3

我有一个关于 GNU MP 的问题，请你帮我解决这个问题。我在 Windows 上使用“GNU 多精度算术库”5.1.1 版。(MinGW\gcc + MSYS)

存在一个 mpz_gcd 函数来计算两个整数的“gcd”。

void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2);

据我从文档中得到的，在 GNU MP 中实现了几种算法，用于计算最大公约数。其中：

  • 二进制 GCD
  • Lehmer 算法
  • 次二次 GCD

使用的算法似乎是根据整数的输入大小自动选择的。

目前，二进制算法仅在 N < 3 时用于 GCD。

对于大于 GCD_DC_THRESHOLD 的输入，通过 HGCD（Half GCD）函数计算 GCD，作为对 Lehmer 算法的推广。

所以，我想至少有三种不同的方法可以得到 gcd(a, b)。我的主要问题：我想自己指定使用哪种算法。我将比较这些算法在随机大输入（即 10^5 位）上的执行时间，以找出一些常见趋势：使用“二进制 GCD”变得比“Lehmer 方法”更差的点是“HGCD-Lehmer”泛化”确实比直接的 Lehmer 等要好。

有没有简单的方法来指定您要使用的算法？从库中提取此算法的任何方式，修改某些“#define”变量的任何方式。是否可以在不重新编译库的情况下做我想做的事情？我只是那里的初学者，我觉得无法弄清楚图书馆里的所有东西。

PS 可能有人会对此感兴趣。我在 github 上有一些代码：https ://github.com/int000h/gcd_gcc

4

1 回答 1

7

这是阅读源代码的好时机。GMP 是开源的——利用它！

在mpn/generic/gcd.c您将找到选择 GCD 算法的函数（这实际上是一个公共函数，它出现在文档中）：

mp_size_t
mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t usize, mp_ptr vp, mp_size_t n)
{
    ...
    if (ABOVE_THRESHOLD (n, GCD_DC_THRESHOLD)) {
        ...

您可以看到该函数有三个主要分支，每个分支都以return语句结尾。每个分支对应一个不同的 GCD 算法。您可以将代码复制并粘贴到您自己的应用程序中并对其进行修改，以便您可以准确指定所需的算法。尖端：

  • 你可以摆脱#ifdefs. 假设TUNE_GCD_P未定义。

  • 这是一个mpn_*函数而不是一个mpz_*函数。它是较低级别的：例如，您必须为输出显式分配空间。您可能还希望从更高级别的函数中复制代码，mpz_gcd().

  • 您需要提取内部函数的原型，例如mpn_hgcd_matrix_adjust(). 只需从 GMP 源代码中复制原型即可。别担心，内部函数似乎是从共享库中导出的（它们通常不应该是，但它们是，所以你很好）。

无需重新编译库，但您需要在这里做一些工作。

于 2013-02-20T01:05:04.430 回答