GNU MP库的GCD计算问题

Question

我有一个关于GNU MP的问题,请你帮我解决一下这个问题.我在Windows上使用"GNU Multiple Precision Arithmetic Library"Edition 5.1.1.(MinGW\gcc + MSYS)

存在一个mpz_gcd函数来计算两个整数的"gcd".

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

据我所知,在GNU MP中实现了几种算法来计算最大公约数.其中:

• 二进制GCD
• 莱默的算法
• 次级GCD

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

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

对于大于GCD_DC_THRESHOLD的输入,GCD通过HGCD(半GCD)函数计算,作为Lehmer算法的推广.

所以,我想至少有三种不同的方法来获得gcd(a,b).对我来说主要问题是:我想指定自己使用哪种算法.我会在随机大输入(即10 ^ 5位)上比较这些算法的时间执行情况,以找出一些常见趋势:使用"二进制GCD"变得比"Lehmer方法"更差的那一点是"HGCD-Lehmer"概括"真的比直截了当的莱默等更好.

有没有简单的方法来指定您想要使用的算法？任何方法从库中提取此算法,任何方式来修改一些"#define"变量.是否可以在没有库重新编译的情况下执行我想要的操作？我只是初学者,我觉得无法弄清楚图书馆里面的各种事情.

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

Answer 1

这是阅读源代码的好时机.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源代码即可.不用担心,内部函数似乎是从共享库中导出的(它们通常不应该是,但它们是,所以你很好).

无需重新编译库,但您需要在此处进行一些工作.