Cycle Finding Problem

1. Introduction

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.

2. Custom Input

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

  1. Random: The function will be f(x) = (x2 - 1) % M and only M and the x0 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 x0 (ranging from 0 to M-1).

You can also set custom x0, 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 x0 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 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)).