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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
You can define custom function f(x) = (A*x2 + B*x + C) % M here.
- Random: The function will be f(x) = (x2 - 1) % M and only M and the x0 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 x0 (ranging from 0 to M-1).
You can also set custom x0, which must be ∈ [0..M-1].
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
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).
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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)).
We reset hare back to x0 and keep tortoise at its current position.
Then, we iteratively advance both pointers to their next values by one step as this maintains the gap of tortoise and hare by kλ.
The first time both pointers are equal tells us the value of μ.
Again, we let tortoise stays in its current position and set hare next to it.
Then, we iteratively move hare to the next value by one step.
The first time both pointers are equal tells us the value of λ.
The animation of this algorithm should clear up most questions involving this algorithm.
We will expand this e-Lecture slides to contain more information about this algorithm later.
You are allowed to use/modify our implementation code for Floyd Cycle-Finding Algorithm:
UVa00350.cpp
UVa00350.java
UVa00350.py
UVa00350.ml
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Random
Custom(a, b, c, m, z0)