= Brent cycle-finding algorithm
{c}
= Brent cycle detection
{c}
{synonym}
For a deterministic iteration $x_{i+1}=f(x_i)$ with eventual cycle length $\lambda$ and preperiod $\mu$, the <Brent cycle-finding algorithm> detects repetition using constant <auxiliary space>.
Hold a checkpoint fixed while another pointer advances through blocks of lengths $1,2,4,8,\ldots$. At a block boundary, move the checkpoint to the advancing pointer and double the next block length. Compare each new state to the checkpoint. Once the checkpoint lies on the cycle and its block is long enough, the first equality occurs exactly $\lambda$ steps after the checkpoint.
To locate the entrance, restart two pointers at the initial state, advance one by $\lambda$ steps, then move both one step at a time until they agree. Before index $\mu$, the first pointer is outside the cycle; at $\mu$ both reach the same cyclic position. The procedure uses $O(\mu+\lambda)$ evaluations of $f$ and constant <auxiliary space>, assuming constant-cost state equality and copying. An infinite nonperiodic orbit has no finite detection guarantee.<An improved Monte Carlo factorization algorithm by Richard P. Brent>[sections 3–4]{ref}
Back to article page