对大量数字使用 GCD

Question

我正在使用 PARI/GP，这是一个数学程序，具有一些对数论有用的功能，特别是因为它支持开箱即用的非常大的整数。对于以前的 C++ 项目，我不得不使用一个名为 BigInt 的库。

目前，使用 PARI/GP，我正在使用

gcd()

函数来计算长度从 0 到 255 digits 的数字的最大公约数 (GCD)，因此您可以想象数字确实变得非常大！我设置

a=0

然后我的循环向上迭代，每次计算

gcd(a,b)

其中

b

是一个永远不会改变的长固定数。

我在想，也许我应该使用欧拉的方法来计算 GCD，我认为这是以下简单的公式：

gcd(b, a % b)

其中

%

符号表示模数。希望我得到的变量顺序正确！

是否有一种粗略而快速的方法来近似计算上面显示的哪种 GCD 方法最快？当然，我会对其他更快的方法持开放态度。

我不希望我的算法永远完成，这只是一个实验，看看它可以根据我用来计算 GCD 的方法达到多远。

Answer 1

二进制 GCD 通常比朴素的 Euclid 好，但是

a

与

b

相比非常小是一种特殊情况，可能会导致二进制 GCD 性能不佳。我会尝试一轮 Euclid，即

gcd(b, a%b)

其中

gcd

是二进制 GCD。

（但不知道这里的潜在问题，我不确定这是最好的建议。）

Answer 2

最好的方法是让 pari 为您完成工作。

• 首先，您可以计算存储在向量 v 中的大量输入的 gcd 作为

  gcd(v)

  .

  ? B=10^255; v = vector(10^6,i,random(B));
  ? gcd(v);
  time = 22 ms.
  ? a = 0; for(i = 1, #v, a = gcd(a,v[i]))
  time = 232 ms. \\ much worse
  

在这样的 small 输入上，这要快得多有两个原因：一方面是循环开销和变量赋值，另一方面是提前中止（一旦中间答案为 1，我们就可以停止）。例如，您可以将 v 乘以 2，以防止第二次优化；简单的

gcd(v)

将保持更快 [因为循环和分配开销仍然存在，但在 C 中而不是在解释的 GP 中；对于小输入，这个开销是very显着的，随着尺寸的增加，它会变得微不足道]

• 类似地，让

  gcd

  函数自己计算出如何最好地计算

  gcd(a,b)

  应该总是比尝试使用诸如

  gcd(b, a % b)

  之类的技巧来“改进”事情更快[注意：顺序没关系，如果 b = 0，这将出错，

  gcd

  足够聪明来检查]。

  gcd(a, b-a)

  不会出错，但平均会减慢速度。例如，如果

  a

  和 b 的大小差异很大，gcd(a,b) 将尝试初始欧几里德步骤，尝试自己添加它应该没有帮助。

• 最后，具体使用的算法取决于底层的多精度库；本地 PARI 或 GNU 的 GMP，后者由于高度优化的实现而更快。在这两种情况下，随着操作数大小的增加，这包括欧几里德算法，二进制加/减 [除以 2 的幂，我们可以假设 a，b 为奇数，然后如果 a = b mod 4 则使用

  gcd(b,(a-b)/4)

  ，否则使用

  gcd(b, (a+b)/4)

  ；除法只是二进制移位]，并且是渐近快速的半 gcd（位大小几乎是线性的）。后者几乎肯定不会在您的计算中使用，因为阈值应该超过 10.000 个十进制数字。另一方面，欧几里得算法将仅用于微小的（字大小）操作数，但由于所有算法都是递归的，因此当大小变得足够小时，它最终会被使用。

如果您想研究

gcd

函数的速度，请尝试使用大约 100.000 十进制数字的整数（然后将其大小加倍），您应该观察到几乎线性的复杂性。