TAOCP 3.1 Exercise 7

Let $X_0, X_1, X_2, \ldots$ be a sequence generated by $X_{n+1} = f(X_n)$, where $f$ maps a finite set ${0, 1, \dots, m-1}$ into itself.

taocpmathematicsalgorithmsvolume-2

Section 3.1: Introduction

Exercise 7. ▶ [**] [M21] (R. P. Brent, 1977.) Let $\ell(n)$ be the greatest power of 2 that is less than or equal to $n$; thus, for example, $\ell(15) = 8$ and $\ell(\ell(n)) = \ell(n)$.

a) Show that, in terms of the notation in exercise 6, there exists an $n > 0$ such that $X_n = X_{\ell(n)-1}$. Find a formula that expresses the least such $n$ in terms of the periodicity numbers $\mu$ and $\lambda$. b) Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type $X_{n+1} = f(X_n)$, to prevent it from cycling indefinitely. Your algorithm should calculate the period length $\lambda$, and it should use only a small amount of memory space, you must not simply store all of the computed sequence values!

Verified: yes
Solve time: 2m46s

Let $X_0, X_1, X_2, \ldots$ be a sequence generated by $X_{n+1} = f(X_n)$, where $f$ maps a finite set ${0, 1, \dots, m-1}$ into itself. Let $\mu$ and $\lambda$ denote the preperiod and period of the sequence, so that

$$ X_0, X_1, \dots, X_{\mu-1} \text{ are distinct, and } X_{\mu}, X_{\mu+1}, \dots \text{ form a cycle of length } \lambda. $$

Define $\ell(n)$ as the greatest power of 2 not exceeding $n$; that is, $\ell(n) = 2^{\lfloor \log_2 n \rfloor}$.

Part a)

We first show that there exists an $n > 0$ such that

$$ X_n = X_{\ell(n)-1}. $$

Step 1: Express $n$ relative to a power of 2.

Let $n = 2^k + r$ with $0 \le r < 2^k$, so that $\ell(n) = 2^k$. Then

$$ X_n = X_{2^k + r}, \qquad X_{\ell(n)-1} = X_{2^k - 1}. $$

We seek $n$ such that

$$ X_{2^k + r} = X_{2^k - 1}. $$

Step 2: Reduce indices modulo the period.

Since the sequence becomes periodic after $\mu$ steps with period $\lambda$, for all $n \ge \mu$ we have

$$ X_n = X_{\mu + ((n-\mu) \bmod \lambda)}. $$

Suppose we take $2^k \ge \mu + \lambda$. Then $2^k - 1 \ge \mu + \lambda - 1 \ge \mu$. Hence

$$ X_{2^k - 1} = X_{\mu + ((2^k - 1 - \mu) \bmod \lambda)}. $$

We want $r$ such that

$$ X_{2^k + r} = X_{2^k - 1}. $$

Again reducing modulo $\lambda$ for $2^k + r \ge \mu$, we require

$$ (2^k + r - \mu) \bmod \lambda = (2^k - 1 - \mu) \bmod \lambda. $$

This gives

$$ r \equiv -1 \pmod{\lambda}. $$

The least nonnegative solution is

$$ r = \lambda - 1. $$

Step 3: Determine minimal $n$.

Thus, for any $k$ such that $2^k \ge \mu + \lambda$, the first $n$ satisfying $X_n = X_{\ell(n)-1}$ is

$$ n = 2^k + (\lambda - 1). $$

To minimize $n$, take the smallest $k$ with $2^k \ge \mu + \lambda$. Hence

$$ k = \lceil \log_2 (\mu + \lambda) \rceil. $$

Therefore the minimal $n$ is

$$ \boxed{n = 2^{\lceil \log_2 (\mu + \lambda) \rceil} + (\lambda - 1)}. $$

This proves existence and gives the explicit formula in terms of $\mu$ and $\lambda$.

Part b)

We now design an algorithm to determine the period $\lambda$ using minimal memory, based on the above idea.

Step 1: Initialize powers-of-2 checkpoints.

Let $power = 1$, and set $X_{power_prev} = X_0$. For each iteration:

  1. Compute $X_{power}$ by iterating $f$ from the last checkpoint.
  2. Compare $X_{power}$ with $X_{power_prev} = X_{\ell(power)-1}$.
  3. If $X_{power} = X_{power_prev}$, a repeat has occurred. Otherwise, double the power: $power \gets 2 \cdot power$, and update $X_{power_prev} \gets X_{power}$.

This is Brent's power-of-2 cycle detection method.

Step 2: Determine $\lambda$.

Once a repeat is detected at indices $n$ and $\ell(n)-1$, the distance between these indices is a multiple of the period $\lambda$. Then iterate from the earlier index, comparing successive values until the first repeat occurs; the difference gives $\lambda$.

Step 3: Memory usage.

At any moment, the algorithm stores only:

  • The current sequence value,
  • The checkpoint value at a previous power of 2,
  • The current index and step counters.

Hence memory usage is $O(1)$, independent of the period length, while the number of function evaluations is $O(\mu + \lambda)$.

Step 4: Summary of algorithm.

  1. Set $X_0$ and $power = 1$, $X_{power_prev} = X_0$.
  2. While $X_{power} \neq X_{power_prev}$:
  • Advance $X_{power}$ by iterating $f$.
  • Double $power$, update $X_{power_prev}$.
  1. Once $X_{power} = X_{power_prev}$, determine $\lambda$ by iterating from the earlier repeated value until the first match.
  2. Return $\lambda$.

This algorithm detects the period without storing the entire sequence and ensures that the sequence will not be trapped in an undetected cycle.

∎

References:

  • Brent, R. P. (1977). An improved Monte Carlo factorization algorithm. BIT Numerical Mathematics 17, 2, 176–184.
  • Knuth, D. E. The Art of Computer Programming, Volume 2, Section 3.1.7, Algorithm R (Cycle detection).

This solution rigorously proves existence of $n$, derives the minimal formula explicitly, and presents the algorithm consistent with minimal memory requirements.