#
__
Cycle Finding Problem
__

##
1. Introduction

Assume that you have a function **f: S → S** and any initial value **x**_{0} ∈ S

(in this visualization, we are restricted to **f(x) = (A*x^2 + B*x + C) % M** and **x**_{0} % M hence the function **f** has domain and range ∈ [0..**M**-1]).

The sequence of iterated function values:

**{x**_{0}, x_{1} = f(x_{0}), x_{2} = f(x_{1}), ..., 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**_{0}.

##
2. Custom Input

You can define custom function **f(x) = (A*x**^{2} + B*x + C) % M here.

- Random: The function will be
**f(x) = (x**^{2} - 1) % M and only **M** and the **x**_{0} are randomly generated. - 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**_{0} (ranging from 0 to **M-1**).

You can also set custom **x**_{0}, 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**_{0} 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**_{0}.

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