Cycle Finding Problem

1. Introduction

Assume that you have a function f: S → S and any initial value x₀ ∈ S
(in this visualization, we are restricted to f(x) = (A*x^2 + B*x + C) % M and x₀ % M hence the function f has domain and range ∈ [0..M-1]).

The sequence of iterated function values:
{x₀, x₁ = f(x₀), x₂ = f(x₁), ..., x_i = f(x_i-1), ...}
must eventually use the same value twice (cycle), i.e. a ≠ b such that x_a = x_b.
Afterwards, the sequence must continue by repeating the cycle of values from x_a to x_b-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 x₀.

2. Custom Input

You can define custom function f(x) = (A*x² + B*x + C) % M here.

1. Random: The function will be f(x) = (x² - 1) % M and only M and the x₀ are randomly generated.
2. Custom: You can specify the coefficients A, B, C of f(x) (ranging from -999 to 999), the modulo value M (ranging from 10 to 1000) and the initial value x₀ (ranging from 0 to M-1).

You can also set custom x₀, which must be ∈ [0..M-1].

3. Floyd's Tortoise-Hare Algorithm

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.

3-1. The Visualization

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 x₀ nicely visualizes μ and λ.

VisuAlgo uses green vertices to represent the tortoise (t) and orange vertices to represent the hare (h).

3-2. Finding kλ (a multiple of λ)

We start from x₀.

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)).