Assume that you have a function f: S → S and any initial value x0 ∈ S
(in this visualization, we are restricted to f(x) = (A*x^2 + B*x + C) % M and x0 % M hence the function f has domain and range ∈ [0..M-1]).
The sequence of iterated function values:
{x0, x1 = f(x0), x2 = f(x1), ..., xi = f(xi-1), ...}
must eventually use the same value twice (cycle), i.e. a ≠ b such that xa = xb.
Afterwards, the sequence must continue by repeating the cycle of values from xa to xb-1.
Let mu (μ) be the smallest index and let lambda (λ) (the cycle length) be the smallest positive integer such that xμ = xμ+λ.
The cycle-finding problem: Find such μ and λ, given f and x0.
You can define custom function f(x) = (A*x2 + B*x + C) % M here.
You can also set custom x0, which must be ∈ [0..M-1].
Floyd's Tortoise-Hare Cycle-Finding is one algorithm that can solve this problem efficiently in both time and space complexities.
It just requires O(μ+λ) time and O(1) space to do the job.
This is the visualization of Floyd's Tortoise-Hare Cycle-Finding algorithm.
The shape of rho (ρ) of the sequence of iterated function values defined by f(x) and x0 nicely visualizes μ and λ.
VisuAlgo uses green vertices to represent the tortoise (t) and orange vertices to represent the hare (h).
We start from x0.
While tortoise's pointer != hare's pointer, we advance tortoise/hare by one step/two steps to their next values by calling f(tortoise)/f(f(hare)).