Brent循环检测算法

Question

能否有人帮我解释一下 Brent 的循环检测算法。我不太明白为什么要 "搜索比 λ 和 μ 都大的最小的 2 的幂次方 2^i"？幂次方2是如何在循环检测中发挥作用的呢？它与 Floyd 的循环检测算法有关吗？从基础知识上来说，我无法理解。请帮忙！

- SlashGeek

---

@WillNess 这与质数有什么关系？我认为应该删除质数标签。 - gsgx

@gsingh2011 它在质因数分解算法中使用。或许应该添加/替换primes标签为prime-factorization... :) - Will Ness

Answer 1

这种方法使用递增的步长（1、2、4、8……）尽快进入循环。当P = 2^k变得大于λ和μ时，乌龟（T）就在循环中，而兔子（H）最多走P步就能再次遇到（站着的）乌龟。仿真似乎会有用。让我们假设列表为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 !!!!!

注意: 当P=4时，T在循环内部，但兔子没有经过整个周期（P>=μ但P<λ）

因此，我们发现μ<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。

- MBo

---

你能解释一下为什么这里要使用“二的幂”吗？如果我们的目标是尽快让兔子进入循环，为什么不使用“三的幂”或“五的幂”？如果使用“五的幂”，这个算法还有效吗？最后，为什么λ等于乌龟和兔子相遇前兔子走的最后步数？我们有什么证明可以把这个数字作为循环长度？谢谢。 - carawan

@carawan，我猜power-of-3和power-of-5也可以，虽然我没有证据。我进行了一些简单的测试。<br/> 如果较慢的迭代器根本不移动，则算法是错误的，因为较慢的迭代器可能在循环外部。<br/> 如果较慢的迭代器紧随快速迭代器，并且以下距离始终低于固定限制（如99），则算法是错误的，因为循环大小可能超过99。<br/> 如果以下距离逐渐增加，并且跟随者确实移动，则我认为最终他们会相遇。 - Bin TAN - Victor