1

前段时间，我将Pollard-Brent 算法的 Python 实现移植到 Clojure。它可以工作，而且工作速度也很快；那不是问题。并且当给定相同的非随机种子值和步进函数时，它会准确地再现 Python 代码的兔子和乌龟位置。

但是当我在研究它时，我不禁注意到乌龟和野兔的移动方式与我预期的基于布伦特论文（或维基百科或任何其他参考选择）。

具体来说，在乌龟传送到兔子的位置后，兔子会向前走distance几步，然后再多走distance几步。此外，在 Brent-Pollard 算法中，中间值也很重要；但是，此代码仅保存了第二个野兔“路径”的步骤。

以下是 Python 代码的第 6-18 行，附有我的评论：

    while g==1:    

        # Tortoise (x) moves to hare (y)         
        x = y 

        # Hare (y) moves ahead by r steps
        for i in range(r):
            y = ((y*y)%N+c)%N

        k = 0

        # Hare (y) moves ahead by another r steps, 
        # with checkpoints at every m steps (the checkpoints are 
        # for the factorization; not part of Brent's cycle-finding algo proper)
        while (k<r and g==1):
            ys = y
            for i in range(min(m,r-k)):
                y = ((y*y)%N+c)%N
                q = q*(abs(x-y))%N
            g = gcd(q,N)
            k = k + m

我今天回顾了我的代码，并决定通过模拟一个简化版本来显示索引来确保测试它。这些是当前代码给出的索引：

当前版本：

Distance: 1
Tortoise at: 1
Hare starts at: 2
Hare path: [3]
Distance: 2
Tortoise at: 3
Hare starts at: 5
Hare path: [6 7]
Distance: 4
Tortoise at: 7
Hare starts at: 11
Hare path: [12 13 14 15]
Distance: 8
Tortoise at: 15
Hare starts at: 23
Hare path: [24 25 26 27 28 29 30 31]
Distance: 16
Tortoise at: 31
Hare starts at: 47
Hare path: [48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63]
Distance: 32
Tortoise at: 63
Hare starts at: 95
Hare path: [96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127]

同时，这是我期望算法做的：

预期输出：

Distance: 1
Tortoise at: 1
Hare path: [2]
Distance: 2
Tortoise at: 2
Hare path: [3 4]
Distance: 4
Tortoise at: 4
Hare path: [5 6 7 8]
Distance: 8
Tortoise at: 8
Hare path: [9 10 11 12 13 14 15 16]
Distance: 16
Tortoise at: 16
Hare path: [17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32]
Distance: 32
Tortoise at: 32
Hare path: [33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64]

即使将“预期”版本结合到算法中时在 Clojure 中的读取效果更好，但平均需要两倍的时间（这是有道理的，查看索引）。

我的问题：

  1. 我的预期输出是布伦特算法的“规范”版本吗？
  2. 当前版本仍然是布伦特算法的正确实现吗？
  3. 为什么即使野兔路径不包含完全连续的索引，当前版本也能工作？
4

0 回答 0