algorithmgraph-theoryprimescycle

Brent's cycle detection algorithm


Can anyone please help me out with Brent's cycle detection algorithm . I m not understanding exactly why "search for the smallest power of two 2^i that is larger than both λ and μ" ? How powers of 2 are playing role in the detection of cycle . Is it somehow related to Floyd's cycle detection algorithm ? I m unable to get it from the basics . Please help !


Solution

  • This method uses increasing steps (1, 2, 4, 8...) to get inside the loop as soon as possible. When P = 2^k becomes larger than both λ and μ, then tortoise (T) is in the loop, and hare (H) makes no more than P steps to meet (standing) tortoise again. It seems that some simulation would be useful. Let's we have list 0-1-2-3-4-5-6-7-3

    P=1 T=0 H=0; H makes 1 step and doesn't meet T
    P=2 T=1 H=1; H makes 2 steps and doesn't meet T
    P=4 T=3 H=3; H makes 4 steps and doesn't meet T 
    P=8 T=7 H=7; H makes 5 steps and meets T !!!!!
    

    Notice: With P=4 T is inside the loop, but hare doesn't go through the whole cycle (P >= μ but P < λ )

    So we have found μ<8 and λ=5. Then we want to find μ (loop entry point)

    T=0 H=0; H makes 5 steps; H=5 
    while T <> H 
       move both
    T=1 H=6
    T=2 H=7
    T=3 H=3 !!!!!!!
    

    We've just found μ=3