VisuAlgo - Cycle-Finding (Floyd's/Tortoise-Hare Algorithm)
source link: https://visualgo.net/en/cyclefinding?slide=1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK