Editing Cycle detection (section)

===Brent's algorithm===

[[Richard Brent (scientist)|Richard P. Brent]] described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.<ref name="brent">{{citation|first=R. P.|last=Brent|author-link=Richard Brent (scientist)|title=An improved Monte Carlo factorization algorithm|journal=[[BIT Numerical Mathematics ]]|volume=20|year=1980|pages=176–184|url=https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf|doi=10.1007/BF01933190|issue=2|s2cid=17181286}}.</ref> However, it is based on a different principle: searching for the smallest [[power of two]] {{math|2<sup>''i''</sup>}} that is larger than both {{mvar|λ}} and {{mvar|μ}}. For {{math|1=''i'' = 0, 1, 2, ...}}, the algorithm compares {{math|''x''<sub>2<sup>''i''</sup>&minus;1</sub>}} 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 {{mvar|λ}} 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 {{mvar|f}} rather than three.<ref>{{harvtxt|Joux|2009}}, Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.</ref>

The following Python code shows how this technique works in more detail.
<syntaxhighlight lang="python">
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):
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu
</syntaxhighlight>

Like the tortoise and hare algorithm, this is a pointer algorithm that uses {{math|''O''(''λ'' + ''μ'')}} tests and function evaluations and {{math|''O''(1)}} storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the [[Pollard rho algorithm]] by around 24%. He also performs an [[Average-case complexity|average case]] analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.<ref name="brent"/>