如何使用 GMP 高效地添加 3 个大整数

Question

我想对 ~2048 位有符号整数执行 x = a + b + c。目前我的代码看起来像

mpz_add(x, a, b);
mpz_add(x, x, c);

有一个函数可以做到这一点吗？这种情况在我的应用程序中发生过很多次。我已经分析了我的代码，并且 3 路添加步骤占用了运行时的很大一部分。如果有一种替代方法可以一次性完成此操作，这可能会有所帮助。

Answer 1

我广泛使用了 MPFR，并且几乎浏览了文档的每个部分。我几乎可以肯定 MPFR 中不存在这样的情况，因此，我几乎可以肯定 GMP 中不存在这样的情况。

一种解决方案可能是切换到 MPFR 并使用 Pavel Holoborodko 的 MPFR C++，它添加了 MPFR 函数的运算符。我无法想象这会对性能有所帮助（尽管它可能不会对其产生太大影响），它是在 GPL 下，并且您必须安装另一个库，但它会合并操作。

我不知道有什么快速算法可以在添加三个数字时不只是添加其中两个，然后在幕后添加最后一个数字。我不认为使用任何语言的任何库将这两个操作组合成一个操作会提高性能。即使使用 GNU MP，任意精度也很慢。如果有帮助的话，我在代码审查中比较了here的速度。

Answer 2

调用两次函数不会产生明显的开销。然而，如果需要，x 的重新分配可能会非常慢。为了避免这种情况，您可以测量 a、b 和 c 的大小，并确保 x 分配了三个数字的最大大小加上 2（在最坏的情况下，1 位用于加法）。您可以使用

mpz_init2(x, maxsize+2);

或者，如果 x 已经初始化，

if (mpz_sizeinbase(x, 2) < maxsize+2)
  mpz_realloc2(x, maxsize+2);

Answer 3

我认为最好的选择是调用该函数两次。如果你不喜欢这样，你可以先设置a=b+c。这将使您可以重复使用。

mpz_add(a,b,c);
mpz_add(x,x,a);
mpz_add(z,z,a); //Use again: i.e. adding a sum to two different numbers