ब्रेंट का चक्र पहचान एल्गोरिदम

Question

क्या कोई भी ब्रेंट के चक्र पहचान एल्गोरिदम के साथ मेरी मदद कर सकता है। मैं बिल्कुल समझ नहीं पा रहा हूं कि क्यों "दो 2^की छोटी शक्ति की खोज करें जो कि λ और μ दोनों से बड़ा है"? चक्र की पहचान में 2 की शक्तियां कैसे भूमिका निभा रही हैं। क्या यह किसी भी तरह फ़्लॉइड के चक्र पहचान एल्गोरिदम से संबंधित है? मैं इसे मूल बातें से प्राप्त करने में असमर्थ हूं। कृपया सहायता कीजिए !

Answer 1

यह विधि लूप के अंदर जितनी जल्दी हो सके बढ़ने के लिए बढ़ते चरणों (1, 2, 4, 8 ...) का उपयोग करती है। जब पी = 2^के λ और μ दोनों से बड़ा हो जाता है, तो कछुए (टी) लूप में होता है, और खरगोश (एच) फिर से कटाई (खड़े) को पूरा करने के लिए पी चरणों से अधिक नहीं बनाता है। ऐसा लगता है कि कुछ सिमुलेशन उपयोगी होगा। चलो हमारे पास सूची 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 !!!!! 

नोटिस: के साथ पी = 4 टी पाश अंदर है, लेकिन खरगोश पूरे चक्र के माध्यम से जाना नहीं है (पी> = μ लेकिन पी < λ)

तो हमें μ < 8 और λ = 5 मिला है। फिर हम μ (पाश प्रवेश बिंदु)

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

हम सिर्फ पाया है पता लगाना चाहते हैं μ = 3