Brent's cycle detection algorithm

Question

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 !

Answer 1

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