c - 用于任意精度算术的 GCD 算法

Question

我完全被这个问题困住了，所以我正在寻求任何帮助。

我想每个人都知道基本的 GCD 计算算法，例如二进制或欧几里得 GCD。实现这样一个计算两个单精度数的方法不是问题。实际上，这只是几笔而已。

我需要为多精度数字(超过 10^5 位)实现此方法(用 C 语言)。有几个可用的 GNU 库(GNU MP、MPFR、MPIR)，它们可以定义多精度数字并对其执行操作。它看起来像一个多精度数字存储在内存中作为一对单精度部分，也就是“肢体”。

它们实现了一些用于查找 gcd(a, b) 的方法，但实际上它们很难满足我的需要。仅当 a 和 b 恰好包含两个肢体时才使用 GCD 计算的二进制方法。当 min(a,b) 包含多于(即 630)个肢体等时使用的 HGCD 方法。我发现很难弄清楚，如何扩展这些方法中的任何一个以用于任何长度的 a 和 b。我还发现不同版本的 GNU 库包含不同版本和方法的 GCD 算法。

问题:我想知道是否有可能使二进制 GCD 算法与“肢体”方面任意长度的多精度整数一起工作，如果可能的话 - 得到任何帮助或想法如何在 C 中实现它。有没有人有任何想法或代码部分如何实现它？

我想考虑解决该问题的任何建议或任何其他解决方案。

如果有人愿意看，这里是 GNU MP 二进制 GCD 方法的一部分(a = b = 2 个肢体):

/* Use binary algorithm to compute G <-- GCD (U, V) for usize, vsize == 2.
   Both U and V must be odd. */
static inline mp_size_t
gcd_2 (mp_ptr gp, mp_srcptr up, mp_srcptr vp)
{
  printf("gcd_2 invoked\n");
  mp_limb_t u0, u1, v0, v1;
  mp_size_t gn;

  u0 = up[0];
  u1 = up[1];
  v0 = vp[0];
  v1 = vp[1];

  ASSERT (u0 & 1);
  ASSERT (v0 & 1);

  /* Check for u0 != v0 needed to ensure that argument to
   * count_trailing_zeros is non-zero. */
  while (u1 != v1 && u0 != v0)
    {
      unsigned long int r;
      if (u1 > v1)
  {
    sub_ddmmss (u1, u0, u1, u0, v1, v0);
    count_trailing_zeros (r, u0);
    u0 = ((u1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (u0 >> r);
    u1 >>= r;
  }
      else  /* u1 < v1.  */
  {
    sub_ddmmss (v1, v0, v1, v0, u1, u0);
    count_trailing_zeros (r, v0);
    v0 = ((v1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (v0 >> r);
    v1 >>= r;
  }
    }

  gp[0] = u0, gp[1] = u1, gn = 1 + (u1 != 0);

  /* If U == V == GCD, done.  Otherwise, compute GCD (V, |U - V|).  */
  if (u1 == v1 && u0 == v0)
    return gn;

  v0 = (u0 == v0) ? ((u1 > v1) ? u1-v1 : v1-u1) : ((u0 > v0) ? u0-v0 : v0-u0);
  gp[0] = mpn_gcd_1 (gp, gn, v0);

  return 1;
}

CodePaste of the above .

Answer 1

专门针对这个问题编写自己的代码，为什么不呢？ (10^9)^2 适合 64 位 int，因此您可以使用 base-(10^9) 数字，每个保存在 64 位整数中。要表示 2^(10^5) 位值，2^(10^5) ~= 10^30103，即具有 ~ 30103 个十进制数字的值，您将对于所涉及的两个数字中的每一个，只需要 30103/9 ~= 3350 整数，这是一个内存中的 ~ 27 kB 数组。

According to WP, for binary GCD algorithm你只需要 minus 和 /2 这很容易通过将每个数字减半来实现，偶尔将 5*10^8 进位到较低的位置数字 (94/2 = 47 = {4,5+2})。最终乘以 2^k 可以使用朴素算法完成，因为它只需要完成一次。

以 10 为基数打印将是微不足道的。如果您不关心最终结果的打印，那么您将不需要最终乘法(或者如果您将结果报告为 2^k*x)，然后您可以使用base-10^18 数字，将要使用的数字减半。

您只需要使用通常的 C 整数算法来处理数字。