Editing Cycle detection (section)

===Floyd's tortoise and hare===
[[File:Tortoise and hare algorithm.svg|thumb|upright=1.25|Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...]]
'''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]].<ref name="knuth">{{citation|first=Donald E.|last=Knuth|author-link=Donald Knuth|title=The Art of Computer Programming, vol. II: Seminumerical Algorithms|publisher=Addison-Wesley|year=1969|page=7, exercises 6 and 7}}</ref><ref>''Handbook of Applied Cryptography,'' by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, [https://books.google.com/books?id=nSzoG72E93MC&pg=PA125 p. 125], describes this algorithm and others</ref> 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,<ref>{{citation|last=Floyd|first=R.W.|author-link=Robert W. Floyd|title=Nondeterministic Algorithms|journal=J. ACM|pages=636–644|volume=14|issue=4|year=1967|doi=10.1145/321420.321422|s2cid=1990464|doi-access=free}}</ref> 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 [[Mathematical folklore|folk theorem]], not attributable to a single individual.<ref>''The Hash Function BLAKE,'' by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), [https://books.google.com/books?id=nhPmBQAAQBAJ&pg=PA21 p. 21], footnote 8</ref>

The key insight in the algorithm is as follows. If there is a cycle, then, for any integers {{math|''i'' ≥ ''μ''}} and {{math|''k'' ≥ 0}}, {{math|1=''x<sub>i</sub>'' = ''x''<sub>''i'' + ''kλ''</sub>}}, where {{mvar|λ}} is the length of the loop to be found, {{mvar|μ}} is the index of the first element of the cycle, and {{mvar|k}} is a whole integer representing the number of loops. Based on this, it can then be shown that {{math|1=''i'' = ''kλ'' ≥ ''μ''}} for some {{math|''k''}} if and only if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} (if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} in the cycle, then there exists some {{mvar|k}} such that {{math|1=2''i'' = ''i'' + ''kλ''}}, which implies that {{math|1=''i'' = ''kλ''}}; and if there are some {{mvar|i}} and {{mvar|k}} such that {{math|1=''i'' = ''kλ''}}, then {{math|1=''2i'' = ''i'' + ''kλ''}} and {{math|1= ''x''<sub>2''i''</sub> = ''x''<sub>''i'' + ''kλ''</sub>}}).  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 {{mvar|ν}} of a repetition that is a multiple of {{mvar|λ}}. Once {{mvar|ν}} is found, the algorithm retraces the sequence from its start to find the first repeated value {{math|''x''<sub>''μ''</sub>}} in the sequence, using the fact that {{mvar|λ}} divides {{mvar|ν}} and therefore that {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''μ'' + ''v''</sub>}}.  Finally, once the value of {{mvar|μ}} is known it is trivial to find the length {{mvar|λ}} of the shortest repeating cycle, by searching for the first position {{math|''μ'' + ''λ''}} for which {{math|1=''x''<sub>''μ'' + ''λ''</sub> = ''x''<sub>''μ''</sub>}}.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at {{math|''x<sub>i</sub>''}}, and the other (the hare) at {{math|''x''<sub>2''i''</sub>}}. At each step of the algorithm, it increases {{mvar|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 {{math|''i'' &gt; 0}} for which the tortoise and hare point to equal values is the desired value {{mvar|ν}}.

The following [[Python (programming language)|Python]] code shows how this idea may be implemented as an algorithm.

<syntaxhighlight lang="python">
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
</syntaxhighlight>

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 {{math|''O''(''λ'' + ''μ'')}} operations of these types, and {{math|''O''(1)}} storage space.<ref>{{harvtxt|Joux|2009}}, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.</ref>