フロイドの循環検出法
単方向連結リストのループ検出なども典型的なのであるが、形式的(フォーマル)な説明には数列のほうが向いているのでここでは擬似乱数列生成器の例で説明する。ポラード・ロー素因数分解法などで擬似乱数列生成器の分析が重要なため、といったこともある。
通常、擬似乱数列生成器は決定的な動作をするのであるから、生成器の内部状態がもし以前と同一になれば、そこから先はその以前と同一の列が再生成される。一般に内部状態の数は有限であるから、いつかは鳩の巣原理によって、以前に出現したどこかからと同一の列が再現されるはずである。この時「どこかから」というのが曲者で、調査を始めた列の、必ず先頭からであるとは限らないのが難しい所である。例えば理想的な擬似乱数列生成器であれば全ての内部状態を経てから必ず最初に戻るが(そして、そのようになる条件が明らかな生成器の族もあるが)、数列を生成する任意の関数にそのような期待はできない。
ここでは具体的な擬似乱数列生成器として、線形合同法のような、通常、内部状態をそのまま出力とする擬似乱数列生成器を考える(もし、内部状態のごく一部のみが出力されるような擬似乱数列生成器を対象とする場合は、当然のことだが、出力される列ではなく、内部状態の列について考えなければならない)。
関数 f {\displaystyle f} を擬似乱数列生成器とする、次のような擬似乱数列 a i {\displaystyle a_{i}} を考える。
a i + 1 = f ( a i ) {\displaystyle a_{i+1}=f(a_{i})}
ナイーブな方法の一例は、数列をいちいち記録していって、並びが同じ部分を総当り的に探すことである。
このアルゴリズムを可視化する最善の方法は、単方向連結リストのループ検出の場合の図(グラフ(ネットワーク)構造)を作ることである。それはちょうどギリシア文字の ρ {\displaystyle \rho } に似ている。列は、 ρ {\displaystyle \rho } の字の伸びた尻尾の先から始まり、上に登っていき、時計周りに回る。具体的には右図の場合、アルゴリズム中の6回目の繰り返しで a 6 {\displaystyle a_{6}} の位置で一致が検出される。そのまま続けると、さらに6回繰り返したときに、同じ要素で再び一致する。巡回の長さも 6 であるため、その後も常に同じ結果となる。