1.Previous
3.Next

sequence values at these two pointers. The smallest value of for which the tortoise and hare point to equal values is the desired value .

The following Python code shows how this idea may be implemented as an algorithm.

def floyd(f, x0) -> (int, int): """Floyd's cycle detection algorithm.""" # Main phase of algorithm: finding a repetition x_i = x_2i. # The hare moves twice as quickly as the tortoise and # the distance between them increases by 1 at each step. # Eventually they will both be inside the cycle and then, # at some point, the distance between them will be # divisible by the period ?. tortoise = f(x0) # f(x0) is the element/node next to x0. hare = f(f(x0)) while tortoise != hare: tortoise = f(tortoise) hare = f(f(hare)) # At this point the tortoise position, ?, which is also equal # to the distance between hare and tortoise, is divisible by # the period ?. So hare moving in cycle one step at a time, # and tortoise (reset to x0) moving towards the cycle, will # intersect at the beginning of the cycle. Because the # distance between them is constant at 2?, a multiple of ?, # they will agree as soon as the tortoise reaches index u.

1.Previous
3.Next