# Elements of Programming: Transformations and Their Orbits

• Print
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.