Brent's cycle detection algorithm in Python
Cycle detection using a teleporting pointer, typically fewer function evaluations than Floyd's.
- File
brent_cycle_detection.py, 45 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/brent-cycle-detection/. The authors are listed in prov/AW3RN4.jsonl.
from typing import Callable, TypeVar
T = TypeVar("T")
def brent(f: Callable[[T], T], x0: T) -> tuple[int, int]:
"""Return (lam, mu): the cycle length and the tail length of x0, f(x0), ...
Precondition: the sequence is eventually periodic (always true when f
maps a finite set into itself). Uses O(1) memory and fewer than
2 * max(mu + 1, lam) + 2 * lam + 2 * mu evaluations of f.
"""
power = lam = 1 # @line L1
tortoise, hare = x0, f(x0) # @line L2
while tortoise != hare: # @line L3
if power == lam: # @line L4
tortoise = hare # @line L5
power *= 2
lam = 0
hare = f(hare) # @line L6
lam += 1
tortoise = hare = x0 # @line L7
for _ in range(lam): # @line L8
hare = f(hare)
mu = 0 # @line L9
while tortoise != hare: # @line L10
tortoise, hare = f(tortoise), f(hare)
mu += 1
return lam, mu # @line L11
def count_evaluations(f: Callable[[T], T], x0: T) -> tuple[int, int, int]:
"""Run brent and also return the number of calls of f."""
calls = 0
def g(x: T) -> T:
nonlocal calls
calls += 1
return f(x)
lam, mu = brent(g, x0)
return lam, mu, calls
test_brent_cycle_detection.py 42 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/brent-cycle-detection/. The authors are listed in prov/AW3RN4.jsonl.
import random
from brent_cycle_detection import brent, count_evaluations
def rho(f, x0):
seen = {}
x, i = x0, 0
while x not in seen:
seen[x] = i
x, i = f(x), i + 1
return i - seen[x], seen[x]
def test_page_examples() -> None:
nxt = {0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 7, 7: 3}
assert brent(nxt.__getitem__, 0) == (5, 3)
assert count_evaluations(nxt.__getitem__, 0) == (5, 3, 23)
f = lambda x: (x * x + 1) % 255
assert brent(f, 3) == (6, 2)
def test_edges() -> None:
assert brent(lambda x: x, 7) == (1, 0)
assert brent(lambda x: 0, 5) == (1, 1)
assert brent(lambda x: (x + 1) % 10, 0) == (10, 0)
assert brent(lambda x: 1 - x, 0) == (2, 0)
def test_random_functions_against_hashing() -> None:
rng = random.Random(1980)
for _ in range(1000):
n = rng.randrange(1, 60)
table = [rng.randrange(n) for _ in range(n)]
x0 = rng.randrange(n)
lam, mu = rho(table.__getitem__, x0)
got_lam, got_mu, calls = count_evaluations(table.__getitem__, x0)
assert (got_lam, got_mu) == (lam, mu)
assert calls < 2 * max(mu + 1, lam) + 2 * lam + 2 * mu
What the next level needs
- the tests did not run in this build