Algorithmic problem
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.
For any function f that maps a finite set S to itself, and any initial value "x"0 in S, the sequence of iterated function values
formula_1
must eventually use the same value twice: there must be some pair of distinct indices i and j such that "xi" = "xj". Once this happens, the sequence must continue periodically, by repeating the same sequence of values from "xi" to "x""j" − 1. Cycle detection is the problem of finding i and j, given f and "x"0.
Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.
The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.
Example.
The figure shows a function f that maps the set "S" = {0,1,2,3,4,5,6,7,8} to itself. If one starts from "x"0 = 2 and repeatedly applies f, one sees the sequence of values
2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...
The cycle in this value sequence is 6, 3, 1.
Definitions.
Let S be any finite set, f be any endofunction from S to itself, and "x"0 be any element of S. For any "i" ; 0, let "xi" = "f"("x""i" − 1). Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that "xμ" = "x""λ" + "μ". The cycle detection problem is the task of finding λ and μ.
One can view the same problem graph-theoretically, by constructing a functional graph (that is, a directed graph in which each vertex has a single outgoing edge) the vertices of which are the elements of S and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices reachable from starting vertex "x"0 form a subgraph with a shape resembling the Greek letter rho (ρ): a path of length μ from "x"0 to a cycle of λ vertices.
Practical cycle-detection algorithms do not find λ and μ exactly. They usually find lower and upper bounds "μl" &amp;leq; "μ" &amp;leq; "μh" for the start of the cycle, and a more detailed search of the range must be performed if the exact value of μ is needed. Also, most algorithms do not guarantee to find λ directly, but may find some multiple "kλ" ; "μ" + "λ". (Continuing the search for an additional "kλ"/"q" steps, where q is the smallest prime divisor of kλ, will either find the true λ or prove that "k" 
 1.)
Computer representation.
Except in toy examples like the above, f will not be specified as a table of values. Such a table implies "O"(|"S"|) space complexity, and if that is permissible, an associative array mapping xi to i will detect the first repeated value. Rather, a cycle detection algorithm is given a black box for generating the sequence xi, and the task is to find λ and μ using very little memory.
The black box might consist of an implementation of the recurrence function f, but it might also store additional internal state to make the computation more efficient. Although "xi" 
 "f"("x""i"−1) must be true "in principle", this might be expensive to compute directly; the function could be defined in terms of the discrete logarithm of "x""i"−1 or some other difficult-to-compute property which can only be practically computed in terms of additional information. In such cases, the number of black boxes required becomes a figure of merit distinguishing the algorithms.
A second reason to use one of these algorithms is that they are pointer algorithms which do no operations on elements of S other than testing for equality. An associative array implementation requires computing a hash function on the elements of S, or ordering them. But cycle detection can be applied in cases where neither of these are possible.
The classic example is Pollard's rho algorithm for integer factorization, which searches for a factor p of a given number n by looking for values xi and "x""i"+"λ" which are equal modulo p "without knowing p in advance." This is done by computing the greatest common divisor of the difference "xi" − "x""i"+"λ" with a known multiple of p, namely n. If the gcd is non-trivial (neither 1 nor n), then the value is a proper factor of n, as desired. If n is not prime, it must have at least one factor "p" ≤ √"n", and by the birthday paradox, a random function f has an expected cycle length (modulo p) of .
Algorithms.
If the input is given as a subroutine for calculating f, the cycle detection problem may be trivially solved using only "λ" + "μ" function applications, simply by computing the sequence of values "xi" and using a data structure such as a hash table to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to "λ" + "μ", unnecessarily large. Additionally, to implement this method as a pointer algorithm would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.
Floyd's tortoise and hare.
Floyd's cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare.
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.
The key insight in the algorithm is as follows. If there is a cycle, then, for any integers "i" ≥ "μ" and "k" ≥ 0, "xi" = "x""i" + "kλ", where λ is the length of the loop to be found, μ is the index of the first element of the cycle, and k is a whole integer representing the number of loops. Based on this, it can then be shown that "i" = "kλ" ≥ "μ" for some "k" if and only if "xi" = "x"2"i" (if "xi" = "x"2"i" in the cycle, then there exists some k such that 2"i" = "i" + "kλ", which implies that "i" = "kλ"; and if there are some i and k such that "i" = "kλ", then "2i" = "i" + "kλ" and "x"2"i" = "x""i" + "kλ"). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value "x""μ" in the sequence, using the fact that λ divides ν and therefore that "x""μ" = "x""μ" + "v". Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position "μ" + "λ" for which "x""μ" + "λ" = "x""μ".
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at "xi", and the other (the hare) at "x"2"i". At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of "i" ; 0 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 μ.
 # Find the position μ of first repetition. 
 mu = 0
 tortoise = x0
 while tortoise != hare:
 tortoise = f(tortoise)
 hare = f(hare) # Hare and tortoise move at same speed
 mu += 1
 # Find the length of the shortest cycle starting from x_μ
 # The hare moves one step at a time while tortoise is still.
 # lam is incremented until λ is found.
 lam = 1
 hare = f(tortoise)
 while tortoise != hare:
 hare = f(hare)
 lam += 1
 return lam, mu
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.
Brent's algorithm.
Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. However, it is based on a different principle: searching for the smallest power of two 2"i" that is larger than both λ and μ. For "i" = 0, 1, 2, ..., the algorithm compares "x"2"i"−1 with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length λ of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of the function f rather than three.
The following Python code shows how this technique works in more detail.
def brent(f, x0) - ; (int, int):
 """Brent's cycle detection algorithm."""
 # main phase: search successive powers of two
 power = lam = 1
 tortoise = x0
 hare = f(x0) # f(x0) is the element/node next to x0.
 # this assumes there is a cycle; otherwise this loop won't terminate
 while tortoise != hare:
 if power == lam: # time to start a new power of two?
 tortoise = hare
 power *= 2
 lam = 0
 hare = f(hare)
 lam += 1
 # Find the position of the first repetition of length λ
 tortoise = hare = x0
 for i in range(lam):
 # range(lam) produces a list with the values 0,