- 2.1 Transformations
- 2.2 Orbits
- 2.3 Collision Point
- 2.4 Measuring Orbit Sizes
- 2.5 Actions
- 2.6 Conclusions
This chapter is from the book
This chapter is from the book
This chapter is from the book
2.4 Measuring Orbit Sizes
The natural type to use for the sizes o, h, and c of an orbit on type T would be an integer count type large enough to count all the distinct values of type T. If a type T occupies k bits, there can be as many as 2k values, so a count type occupying k bits could not represent all the counts from 0 to 2k. There is a way to represent these sizes by using distance type.
An orbit could potentially contain all values of a type, in which case o might not fit in the distance type. Depending on the shape of such an orbit, h and c would not fit either. However, for a ρ-shaped orbit, both h and c fit. In all cases each of these fits: o – 1 (the maximum distance in the orbit), h – 1 (the maximum distance in the handle), and c – 1 (the maximum distance in the cycle). That allows us to implement procedures returning a triple representing the complete structure of an orbit, where the members of the triple are as follows:
|
Case |
m0 |
m1 |
m2 |
|
Terminating |
h – 1 |
0 |
terminal element |
|
Circular |
0 |
c – 1 |
x |
|
ρ-shaped |
h |
c – 1 |
connection point |
template<typename F>
requires(Transformation(F))
triple<DistanceType(F), DistanceType(F), Domain(F)>
orbit_structure_nonterminating_orbit(const Domain(F)& x, F f)
{
typedef DistanceType(F) N;
Domain(F) y = connection_point_nonterminating_orbit(x, f);
return triple<N, N, Domain(F)>(distance(x, y, f),
distance(f(y), y, f),
y);
}
template<typename F, typename P>
requires(Transformation(F) &&
UnaryPredicate(P) && Domain(F) == Domain(P))
triple<DistanceType(F), DistanceType(F), Domain(F)>
orbit_structure(const Domain(F)& x, F f, P p)
{
// Precondition: p(x) ⇔ f(x) is defined
typedef DistanceType(F) N;
Domain(F) y = connection_point(x, f, p);
N m = distance(x, y, f);
N n(0);
if (p(y)) n = distance(f(y), y, f);
// Terminating: m = h – 1 ∧ n = 0
// Otherwise: m = h ∧ n = c – 1
return triple<N, N, Domain(F)>(m, n, y);
}
Exercise 2.4.
Derive formulas for the count of different operations (f, p, equality) for the algorithms in this chapter.
Exercise 2.5.
Use orbit_structure_nonterminating_orbit to determine the average handle size and cycle size of the pseudorandom number generators on your platform for various seeds.