- 2.1 Transformations
- 2.2 Orbits
- 2.3 Collision Point
- 2.4 Measuring Orbit Sizes
- 2.5 Actions
- 2.6 Conclusions
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 2^{k} values, so a count type occupying k bits could not represent all the counts from 0 to 2^{k}. 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.