Thuật toán phát hiện chu trình của Brent

Question

Bất kỳ ai cũng có thể giúp tôi với thuật toán phát hiện chu trình của Brent. Tôi không hiểu chính xác tại sao "tìm kiếm sức mạnh nhỏ nhất của hai 2^i lớn hơn cả λ và μ"? Làm thế nào quyền hạn của 2 đang chơi vai trò trong việc phát hiện chu kỳ. Có phải nó liên quan đến thuật toán phát hiện chu kỳ Floyd không? Tôi không thể lấy nó từ những điều cơ bản. Hãy giúp tôi !

Answer 1

Phương pháp này sử dụng các bước tăng (1, 2, 4, 8 ...) để vào bên trong vòng lặp càng sớm càng tốt. Khi P = 2^k trở nên lớn hơn cả λ và μ, thì con rùa (T) đang ở trong vòng lặp, và thỏ (H) không làm nhiều hơn các bước P để gặp lại (đứng) rùa một lần nữa. Dường như một số mô phỏng sẽ hữu ích. Chúng ta hãy có danh sách 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 !!!!! 

Lưu ý: Với P = 4 T là bên trong vòng lặp, nhưng thỏ không đi qua toàn bộ chu kỳ (P> = μ nhưng P < λ)

Vì vậy, chúng tôi đã tìm thấy μ < 8 và λ = 5. Sau đó, chúng tôi muốn tìm μ (entry point loop)

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 !!!!!!! 

Chúng tôi vừa tìm thấy μ = 3