web*_*ary 6 algorithm math performance number-theory modular-arithmetic
作为一个业余爱好项目,我正在努力寻找真正庞大的素数.对此的素性测试包含模幂运算,即a ^ modn.让我们称之为modpow操作,以使解释变得简单.我想加快这个特定的计算.
目前我正在使用GMP的mpz_pown函数,但是,它有点慢.我认为它太慢的原因是因为对GMP的modpow的函数调用比对相同大数字的PFGW软件的完整素性测试要慢.(所以要清楚,这只是GMP的modpow部分,而不是我正在比较的整个自定义素性测试程序).PFGW被认为是其领域中最快的,对于我的用例,它使用了Brillhart-Lehmer-Selfridge素性测试 - 它也使用了modpow程序 - 所以不是因为数学上的聪明,PFGW在这方面更快(请纠正我,如果我错了.)看起来GMP的瓶颈是modpow操作.数字的示例运行时间略超过20,000个数字:GMP的modpow操作大约需要45秒,而PFGW在9秒内完成整个素数测试(包括一个modpow).对于更大的数字,差异变得更加令人印象深刻.GMP使用FFT乘法和蒙哥马利减少进行此测试比较,请参阅下面这篇文章的评论.
我做了一些研究.到目前为止,我理解modpow算法通过平方,整数乘法和模数减少使用取幂 - 这些对我来说都非常熟悉.几种辅助方法可以改善整数乘法的运行时间:
为了通过平方部分来改善取幂的运行时间,可以使用有符号的数字表示来减少乘法的数量(即,比特表示为0,1或-1,并且比特串以这样的方式表示,使得它包含的零比原始的base-2表示更多 - 这通过平方减少了求幂的运行时间.
为了优化操作的模数部分,我知道这些方法:
所以这是150,000美元的问题:有一个软件库可以在给定非常大的基数,指数和模数的情况下有效地进行modpow操作吗？(我的目标是数百万的数字).如果您想建议一个选项,请尝试解释算法的内部工作原理,包括基数,模数和指数的数百万位数,因为有些库根据位数使用不同的算法.基本上我正在寻找一个支持上述技术的库(或者可能更聪明的技术),并且它在运行算法时应该运行良好(至少比GMP好).到目前为止,我已经搜索,发现并尝试了GMP和PFGW,但没有发现这些令人满意(PFGW很快,但我只对modpow操作感兴趣并且没有直接的编程接口).我希望可能是该领域的专家可以建议具有这些功能的库,因为似乎很少有能够处理这些要求的库.
编辑:使问题更简洁,因为它标记得太宽泛.
小智 6
首先,重新.答案1作者的评论"我不使用GMP,但我怀疑当他们写作时他们使用FFT他们真的意味着NTT" - 不,当GMP说"FFT"时它意味着浮点FFT.IIRC他们也有一些NTT基于惯例,但对于bignum mul而言,那些与FFT无竞争力.
经过良好调整的FFT-mul击败任何NTT的原因是由于舍入误差累积导致的单字精度的轻微损失超过了现代CPU产品的极佳浮点能力,特别是当考虑到利用CPU的矢量数学功能的高性能实现,例如x86_64系列,其当前的迭代--Intel Haswell,Broadwell和Skylake - 具有大量的矢量浮点功能.(我不会在这方面引用AMD,因为他们的AVX产品远远落后于英特尔;他们的高水位大约是在2002年左右,从那以后英特尔每年都在以逐渐恶化的方式击败它们.)原因这方面的GMP令人失望的是,相对而言,GMP的FFT是废话.我总体上非常尊重GMP编码器,但是FFT时序是FFT时序,你没有获得积分或者例如具有非常好的bignum添加.这是一篇详细介绍了大量GMP FFT-mul改进的文章:
Pierrick Gaudry,Alex Kruppa,Paul Zimmerman:"基于GMP的Schönhage-Strassen大整数乘法算法的实现"[ http://www.loria.fr/~gaudry/publis/issac07.pdf]
这是从2007年开始,但AFAIK下面的片段中记录的性能差距并没有缩小; 如果它有任何扩大的话.本文非常适合详细介绍可以部署的各种数学和算法改进,但让我们切入金钱报价:
"为整数乘法实现复杂浮点FFT的程序是George Woltman的Prime95.它主要用于测试大型Mersenne数字2 ^ p - 1中的普通性,用于Great Internet Mersenne Prime Search [24].用于乘法的一个DWT mod a*2 ^ n±c,a和c不太大,见[17].我们比较了Prime95版本24.14.2中的乘法模2 ^ 2wn - 1与n字整数的乘法运算在3.2 GHz的Pentium 4和2.4 GHz的Opteron 250上实现SSA,参见图4.很明显,Prime95大幅度地实现了我们的实现,实际上通常超过了10倍. Pentium 4,Opteron的亮度为2.5到3倍."
接下来的几段是一大堆节省面子的旋转.(再次,我个人认识了3位作者中的2位,他们都是计算数论领域的顶尖人物.)
请注意前面提到的George Woltman,其Prime95代码自20年前首次亮相后不久就发现了所有世界纪录的素数,使得他的核心bignum例程以一般的API形式提供,称为GWNUM库.你提到PFGW比FFT-mul的GMP快多少 - 这是因为PFGW使用GWNUM进行核心'繁重提升'算法,这就是PFGW中'GW'的来源.
我自己的FFT实现,它具有泛型C构建支持,但像George一样使用大量的x86矢量数学汇编程序来获得该CPU系列的高性能,比目前的英特尔处理器系列上的George慢大约60-70%.我相信这使它成为x86上世界上第二快的bignum-mul代码.举例来说,我的代码当前正在使用30-M双倍FFT(30*2 ^ 20双倍)对大约2 ^ 29位的数字运行素性测试; 因此每个输入字略多于17位.使用我的所有四个3.3 GHz Haswell 4670 quad核心,每个modmul需要约90 ms.
顺便说一句,很多(如果不是大多数)世界顶级的bignum数学编码人员都在mersenneforum.org上闲逛,我鼓励你查看一下,向更广泛的(至少在这个特定领域)专家观众提问.我出现在这里的同一个句柄下面; 乔治·沃尔特曼(George Woltman)出现为"Prime95",PFGW的马克·罗登基希(Mark Rodenkirch)饰演"流氓".