Cycle Detection, in depth: Floyd's tortoise and hare, Brent's algorithm, the rho shape, proofs, linked lists, Pollard's rho and production pitfalls

The shape of every iterated sequence

Draw each value as a node with one outgoing edge to f(x). This is a functional graph: every node has out-degree exactly one. Start anywhere and follow edges, and the path looks like the Greek letter rho: a straight tail of mu distinct values, then a cycle of lambda distinct values that repeats forever. Formally, mu is the smallest index whose value appears again later, and lambda is the smallest positive number with x[mu + lambda] = x[mu]. The tail may be empty (mu = 0, the start is on the cycle) and the cycle may have length one (a fixed point, f(x) = x).

One fact carries all the proofs below: for any i >= mu, x[i] = x[i + k*lambda] for every whole number k. Once you are on the cycle, moving a multiple of lambda steps brings you back to the same value. A graph where a node can have several outgoing edges instead needs depth-first search with colouring, which is a different problem covered in BFS and DFS.

Phase 1: the tortoise and the hare meet

Start two pointers at x0. On each step the tortoise moves one edge and the hare moves two. After i steps the tortoise holds x[i] and the hare holds x[2i]. Stop when they hold equal values.

Why must they meet? Once the tortoise has entered the cycle (i >= mu), both pointers are on it. Each step the hare gains exactly one position on the tortoise around the cycle, so the gap between them, measured modulo lambda, shrinks by one per step. A gap that shrinks by one each step reaches zero within lambda steps. So the first meeting happens at some i no larger than mu + lambda.

What do we know at the meeting? x[i] = x[2i] with both indices on the cycle means the distance between them, which is i itself, is a multiple of lambda. That is the key result of phase 1: the meeting index i is a multiple of lambda and is at least mu. The meeting point itself is usually not the start of the cycle, which is why two more phases follow.

Phase 2 and phase 3: the cycle start and the cycle length

Phase 2 finds mu. Put the tortoise back at x0, leave the hare at the meeting point x[i], and now move both one step at a time. After j steps the tortoise holds x[j] and the hare holds x[i + j]. Since i is a multiple of lambda, those two values are equal exactly when j has reached the cycle, and they are different while the tortoise is still on the tail (tail values never repeat). So they first match at j = mu, and the matching value is the first node of the cycle.

Phase 3 finds lambda. Hold the tortoise at the cycle start and walk the hare forward one step at a time until it returns to the same value, counting steps. Total work is linear in mu + lambda and memory is constant.

def floyd(f, x0):
    """Return (mu, lam): tail length and cycle length of x0, f(x0), f(f(x0)), ..."""
    # Phase 1: find a meeting point; its index is a multiple of lam.
    tortoise, hare = f(x0), f(f(x0))
    while tortoise != hare:
        tortoise, hare = f(tortoise), f(f(hare))

    # Phase 2: restart the tortoise; both move 1 step; they meet at x[mu].
    mu, tortoise = 0, x0
    while tortoise != hare:
        tortoise, hare = f(tortoise), f(hare)
        mu += 1

    # Phase 3: walk once around the cycle from x[mu].
    lam, hare = 1, f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
    return mu, lam

Worked example: tracing it by hand

Use f(x) = (x*x + 1) mod 1000 with x0 = 2. The sequence is 2, 5, 26, 677, 330, 901, 802, 205, then 26 again. Reading the definitions straight off it, mu = 2 and lambda = 6. Now check that the algorithm finds the same thing without ever storing the list.

They meet at i = 6, which is indeed a multiple of lambda = 6 and at least mu = 2. Phase 2 resets the tortoise to 2 while the hare stays on 802. One step: tortoise 5, hare 205. Two steps: tortoise 26, hare 26. They match after 2 steps, so mu = 2 and the cycle starts at 26. Phase 3 walks 677, 330, 901, 802, 205, 26: six steps, so lambda = 6. Counting every call to f in the code above, the whole run costs 28 evaluations.

Brent's algorithm: fewer evaluations when f is expensive

Floyd evaluates f three times per phase-1 step, and the tortoise re-walks values the hare has already computed. Richard Brent's 1980 variant avoids that. Keep a fixed checkpoint and move only one pointer. Search in windows of length 1, 2, 4, 8 and so on: at the start of each window, teleport the checkpoint to the current position, then step forward up to the window size, comparing against the checkpoint. When the window is at least lambda long and the checkpoint is on the cycle, the moving pointer returns to it, and the number of steps taken in that window is lambda directly.

def brent(f, x0):
    power = lam = 1
    checkpoint, hare = x0, f(x0)
    while checkpoint != hare:          # find lam directly
        if power == lam:               # window exhausted: move checkpoint, double window
            checkpoint, power, lam = hare, power * 2, 0
        hare = f(hare)
        lam += 1

    # Find mu: start two pointers lam apart and advance them together.
    tortoise = hare = x0
    for _ in range(lam):
        hare = f(hare)
    mu = 0
    while tortoise != hare:
        tortoise, hare = f(tortoise), f(hare)
        mu += 1
    return mu, lam

On the worked example Brent returns the same mu = 2, lambda = 6 with 23 evaluations against Floyd's 28. The gap widens as f gets more expensive relative to a comparison, which is the situation in factoring and cryptanalysis. Floyd stays popular because its three phases are easy to prove and to review, and on a linked list the difference in pointer loads rarely matters.

Where it runs: linked lists

A singly linked list is a functional graph where f(node) = node.next. A corrupted or deliberately circular list is a rho, and a normal list is a tail ending at null. The algorithm is the same, with one extra rule: the hare must check for null before each of its two steps, because a list without a cycle ends.

def find_cycle_start(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                      # identity, not value equality
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow                       # first node of the cycle
    return None                               # reached the end: no cycle

Two details matter. Compare node identity (is in Python, == on references in Java), not the payload, because two different nodes can hold equal data. And it runs without allocating, which makes it cheap enough to leave in as a debug assertion over any singly linked structure you build or mutate.

Where it runs: Pollard's rho and random-number generators

Pollard's rho factoring method is Floyd's phase 1 wearing a disguise. To factor n, iterate f(x) = (x*x + 1) mod n. If p is an unknown prime factor of n, the same sequence reduced mod p lives in a much smaller set, so it enters its cycle far sooner. When the tortoise and hare collide mod p but not mod n, gcd(|tortoise - hare|, n) is a non-trivial factor. You never know p; the gcd reveals the hidden collision. With n = 8051 and x0 = 2, step 1 gives 5 and 26, step 2 gives 26 and 7474, and step 3 gives 677 and 871, where gcd(194, 8051) = 97: 8051 is 83 times 97. Production implementations use Brent's variant and batch many differences into one product before each gcd.

Any generator whose next state is a pure function of its current state is a functional graph over its state space, so Floyd or Brent measures its period in constant memory. Run it on a reduced state size first: a linear congruential generator with a badly chosen multiplier can have a far shorter cycle than its designer expected, and the tail-and-cycle numbers tell you immediately.

Choosing a method

The hash-set approach is not wrong: when the sequence is known to be short, a set from a hash table is simpler to explain and debug; store each value's first index, not just the value, and the first repeat gives both answers. The constant-memory methods win when the sequence is long, when allocation is forbidden, or when you want a guaranteed upper bound on memory. For the cost model behind these comparisons see Big O analysis. For undirected connectivity questions, where you only need to know whether adding an edge closes a cycle, union-find is the right tool rather than any of these.

Failure modes

• f is not a pure function. If f reads a clock, a random source or mutable shared state, the sequence is not a rho and the algorithm can loop forever or report nonsense. Make the whole state an explicit argument.
• Floating-point states. Equality on floats makes a nearly periodic orbit look aperiodic, and rounding can manufacture false cycles. Quantise to a fixed grid on purpose, or do not use exact cycle detection.
• Overflow. x * x overflows 64-bit integers when n is above about 2 to the 32. Use 128-bit multiplication or a Montgomery form in C, C++, Java or Go.
• Mutation during the walk. Another thread editing a linked list while you traverse it breaks the rho assumption. Take the lock or snapshot first.
• Unbounded loops on huge cycles. A cycle of length 2 to the 64 is finite but will not finish. Add a step budget and treat exhaustion as unknown, not as no cycle.
• Off-by-one in mu or lambda. The most common bug is starting phase 1 with both pointers at x0 and testing equality before moving. Test against the hash-set version on thousands of random small functions.

What to do next

1. Implement floyd and brent from this page and check them against a hash-set reference on random functions over a set of 100 to 1,000 values.
2. Trace f(x) = (x*x + 1) mod 1000 from x0 = 3 by hand before running it, then confirm your answer with the code.
3. Add find_cycle_start as a debug assertion anywhere your code builds or mutates linked structures.
4. Implement Pollard's rho with Brent's variant and a gcd, and factor a few 12-digit semiprimes.
5. Measure the period of a toy generator by shrinking its state to 16 bits and running Brent on it.
6. Wherever you add cycle detection to production code, add a step budget and a test with a deliberately corrupted input.