フロイドの循環検出法
このとき必要な記憶領域は O ( μ + λ ) {\displaystyle O(\mu +\lambda )} であり、 μ {\displaystyle \mu } は循環部分の長さ、 λ {\displaystyle \lambda } は循環していない部分の長さである。
ここで注目すべきは、2つの要素に以下の関係が成り立つとき
a i = a j {\displaystyle a_{i}=a_{j}}
その間の要素数 | i − j | {\displaystyle |i-j|} は循環の長さの整数倍となる。なぜなら、循環数列の定義から、次が成り立つからである。
a λ + m = a λ + m + k μ . {\displaystyle a_{\lambda +m}=a_{\lambda +m+k\mu }.}
この2つの要素のインデックスの差は k μ {\displaystyle k\mu } であり、循環部分の長さの整数倍となっている。フロイドの循環検出法は、2つのインデックス変数を並行して増やしていき(ただし、一方はもう一方の2倍の速度で増やす)、このように一致する場合を探すのである。すなわち一方のインデックスを1ずつ増やし、もう一方を2ずつ増やしていく。すると、ある時点で次のようになる。
a m = a 2 m {\displaystyle a_{m}=a_{2m}}
ここで、 2 m − m = m {\displaystyle 2m-m=m} を割り切れる任意の数が循環の長さとなる(循環に入る前の部分 λ {\displaystyle \lambda } は、 λ > m − μ {\displaystyle \lambda >m-\mu } でかつ λ <= m {\displaystyle \lambda <=m} の任意の値と考えられる)。