- 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.3 Collision Point
If we observe the behavior of a transformation, without access to its definition, we cannot determine whether a particular orbit is infinite: It might terminate or cycle back at any point. If we know that an orbit is finite, we can use an algorithm to determine the shape of the orbit. Therefore there is an implicit precondition of orbit finiteness for all the algorithms in this chapter.
There is, of course, a naive algorithm that stores every element visited and checks at every step whether the new element has been previously encountered. Even if we could use hashing to speed up the search, such an algorithm still would require linear storage and would not be practical in many applications. However, there is an algorithm that requires only a constant amount of storage.
The following analogy helps to understand the algorithm. If a fast car and a slow one start along a path, the fast one will catch up with the slow one if and only if there is a cycle. If there is no cycle, the fast one will reach the end of the path before the slow one. If there is a cycle, by the time the slow one enters the cycle, the fast one will already be there and will catch up eventually. Carrying our intuition from the continuous domain to the discrete domain requires care to avoid the fast one skipping past the slow one.1
The discrete version of the algorithm is based on looking for a point where fast meets slow. The collision point of a transformation f and a starting point x is the unique y such that
y = fn(x) = f2n+1(x) |
and n ≥ 0 is the smallest integer satisfying this condition. This definition leads to an algorithm for determining the orbit structure that needs one comparison of fast and slow per iteration. To handle partial transformations, we pass a definition-space predicate to the algorithm:
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P))
Domain(F) collision_point(const Domain(F)& x, F f, P p)
{
// Precondition: p(x) ⇔ f(x) is defined
if (!p(x)) return x;
Domain(F) slow = x; // slow = f0(x)
Domain(F) fast = f(x); // fast = f1(x)
// n ← 0 (completed iterations)
while (fast != slow) { // slow = fn(x) ∧ fast = f2n+1(x)
slow = f(slow); // slow = fn+1(x) ∧ fast = f2n+1(x)
if (!p(fast)) return fast;
fast = f(fast); // slow = fn+1(x) ∧ fast = f2n+2(x)
if (!p(fast)) return fast;
fast = f(fast); // slow = fn+1(x) ∧ fast = f2n+3(x)
// n ← n + 1
}
return fast; // slow = fn(x) ∧ fast = f2n+1(x)
// Postcondition: return value is terminal point or collision point
}
We establish the correctness of collision_point in three stages: (1) verifying that it never applies f to an argument outside the definition space; (2) verifying that if it terminates, the postcondition is satisfied; and (3) verifying that it always terminates.
While f is a partial function, its use by the procedure is well defined, since the movement of fast is guarded by a call of p. The movement of slow is unguarded, because by the regularity of f, slow traverses the same orbit as fast, so f is always defined when applied to slow.
The annotations show that if, after n ≥ 0 iterations, fast becomes equal to slow, then fast = f2n+1(x) and slow = fn(x). Moreover, n is the smallest such integer, since we checked the condition for every i < n.
If there is no cycle, p will eventually return false because of finiteness. If there is a cycle, slow will eventually reach the connection point (the first element in the cycle). Consider the distance d from fast to slow at the top of the loop when slow first enters the cycle: 0 ≤ d < c. If d = 0, the procedure terminates. Otherwise the distance from fast to slow decreases by 1 on each iteration. Therefore the procedure always terminates; when it terminates, slow has moved a total of h + d steps.
The following procedure determines whether an orbit is terminating:
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P))
bool terminating(const Domain(F)& x, F f, P p)
{
// Precondition: p(x) ⇔ f(x) is defined
return !p(collision_point(x, f, p));
}
Sometimes we know either that the transformation is total or that the orbit is nonterminating for a particular starting element. For these situations it is useful to have a specialized version of collision_point:
template<typename F>
requires(Transformation(F))
Domain(F)
collision_point_nonterminating_orbit(const Domain(F)& x, F f)
{
Domain(F) slow = x; // slow = f0(x)
Domain(F) fast = f(x); // fast = f1(x)
// n ← 0 (completed iterations)
while (fast != slow) { // slow = fn(x) ∧ fast = f2n+1(x)
slow = f(slow); // slow = fn+1(x) ∧ fast = f2n+1(x)
fast = f(fast); // slow = fn+1(x) ∧ fast = f2n+2(x)
fast = f(fast); // slow = fn+1(x) ∧ fast = f2n+3(x)
// n ← n + 1
}
return fast; // slow = fn(x) ∧ fast = f2n+1(x)
// Postcondition: return value is collision point
}
In order to determine the cycle structure—handle size, connection point, and cycle size—we need to analyze the position of the collision point.
When the procedure returns the collision point
fn(x) = f2n+1(x) |
n is the number of steps taken by slow, and 2n + 1 is the number of steps taken by fast.
n = h + d |
where h is the handle size and 0 ≤ d < c is the number of steps taken by slow inside the cycle. The number of steps taken by fast is
2n +1 = h + d + qc |
where q ≥ 0 is the number of full cycles completed by fast when slow enters the cycle. Since n = h + d,
2(h + d)+1 = h + d + qc |
Simplifying gives
qc = h + d + 1 |
Let us represent h modulo c:
h = mc + r |
with 0 ≤ r < c. Substitution gives
qc = mc + r + d + 1 |
or
d = (q – m)c – r – 1 |
0 ≤ d < c implies
q – m = 1 |
so
d = c – r – 1 |
and r + 1 steps are needed to complete the cycle.
Therefore the distance from the collision point to the connection point is
e = r +1 |
In the case of a circular orbit h = 0, r = 0, and the distance from the collision point to the beginning of the orbit is
e = 1 |
Circularity, therefore, can be checked with the following procedures:
template<typename F>
requires(Transformation(F))
bool circular_nonterminating_orbit(const Domain(F)& x, F f)
{
return x == f(collision_point_nonterminating_orbit(x, f));
}
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P))
bool circular(const Domain(F)& x, F f, P p)
{
// Precondition: p(x) ⇔ f(x) is defined
Domain(F) y = collision_point(x, f, p);
return p(y) && x == f(y);
}
We still don’t know the handle size h and the cycle size c. Determining the latter is simple once the collision point is known: Traverse the cycle and count the steps.
To see how to determine h, let us look at the position of the collision point:
fh+d(x) = fh+c-r-1(x) = fmc+r+c-r-1(x) = f(m+1)c-1(x) |
Taking h + 1 steps from the collision point gets us to the point f(m+1)c+h(x), which equals fh(x), since (m + 1)c corresponds to going around the cycle m + 1 times. If we simultaneously take h steps from x and h + 1 steps from the collision point, we meet at the connection point. In other words, the orbits of x and 1 step past the collision point converge in exactly h steps, which leads to the following sequence of algorithms:
template<typename F>
requires(Transformation(F))
Domain(F) convergent point(Domain(F) x0, Domain(F) x1, F f)
{
while (x0 != x1) {
x0 = f(x0);
x1 = f(x1);
}
return x0;
}
template<typename F>
requires(Transformation(F))
Domain(F)
connection_point_nonterminating_orbit(const Domain(F)& x, F f)
{
return convergent point(
x,
f(collision point nonterminating orbit(x, f)),
f);
}
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P))
Domain(F) connection point(const Domain(F)& x, F f, P p)
{
// Precondition: p(x) ⇔ f(x) is defined
Domain(F) y = collision_point(x, f, p);
if (!p(y)) return y;
return convergent point(x, f(y), f);
}
Lemma 2.8.
If the orbits of two elements intersect, they have the same cyclic elements.
Exercise 2.2.
Design an algorithm that determines, given a transformation and its definition-space predicate, whether the orbits of two elements intersect.
Exercise 2.3.
For convergent_point to work, it must be called with elements whose distances to the convergent point are equal. Implement an algorithm convergent_point_guarded for use when that is not known to be the case, but there is an element in common to the orbits of both.