Floyd's cycle-finding algorithm
From CodeCodex
[edit] Python
def floyd(f, x0): # The main phase of the algorithm, finding a repetition x_nu = x_2nu # The hare moves twice as quickly as the tortoise tortoise, hare = f(x0), f(f(x0)) while tortoise != hare: tortoise = f(tortoise) hare = f(f(hare)) # Find the position of the first repetition of length nu # The hare and tortoise move at the same speeds mu = 0 tortoise, hare = x0, tortoise while tortoise != hare: tortoise = f(tortoise) hare = f(hare) mu += 1 # Find the length of the shortest cycle starting from x_mu # The hare moves while the tortoise stays still lam = 1 hare = f(tortoise) while tortoise != hare: hare = f(hare) lam += 1 return lam, mu
Note that this code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses O(λ+μ) operations of these types, and O(1) storage space.
