多核时代下的大数乘法

Ickiverar

gxqcn 发表于 2018-2-28 08:17
第一行就没看明白。

楼上开发的大数库，可有提供下载测试？很想体验一下。。。

https://pan.baidu.com/s/1mjc6Ums
这是我的大数库，还非常简陋，用法和gmp差不多，还没有做并行。

第一行是说，傅里叶变换（FT）的一个性质。
快速傅里叶变换（FFT）就是利用了这个性质的一个特殊情况，把长度为 N 的FT拆成了 先做2个长度为 N/2 的 FT ，再做 N/2 个长度为 2 的 FT 。
其实这样的拆法N= N/2 *2 可以更随意一些，比如 N=N/4 * 4 对应基4的FFT，还有基3的，基5的，基7的，基 $2^{p_1}*3^{p_2}*5^{p_3}*7^{p_4}$ 的等等。

gxqcn

你的大数测试，我已收了。

待我的 x64 版，核心基础模块开发差不多时，可以有个基准参考。
只是近来有许多事要忙，本计划开启的，可能又有变数。

Ickiverar

（我本来想冲击计算圆周率的世界纪录，但看了看现在的记录，我感觉我没那么多钱买硬盘）
我的大数库（ilmp）拥有的函数类型已经足够我计算pi了。但这个库适用的位数还太低（受限于可以申请的连续内存）。
目前我库是单线程的，纯内存的，纯整数的，无错误校验的。使用的算法是 basecase，karatsuba，toomcook33，SSA。

可能的思考方向：

根据一些资料，使用汇编级向量化的复浮点FFT在较短长度（不超过内存或者cpu cache的级别）要更快，但可能出现浮点舍入误差，需要一个简单的checksum。
所以是否应该写点向量化浮点汇编？
http://www.numberworld.org/y-cru ... multiplication.html
“In the past, y-cruncher also had an implementation of 3-way Toom-Cook. But it was never optimal to use on any processor and was removed after v0.5.5. Likewise, no attempt was ever made to implement higher or unbalanced Toom-Cook algorithms. Floating-Point FFT is so fast that it renders all of these more complicated methods completely obsolete. If current hardware trends continue, even Karatsuba multiplication will eventually disappear from future processors.”

根据一些资料，目前世界纪录使用的软件在计算超长乘法时用的是模小质数的NTT，最后用中国剩余定理重组。它用了一些64bit的质数。
所以是否应该尝试一下NTT？

大数库应该有纠错能力，至少对乘法运算，可以检查出到底乘对了没有。

大数库应该有以磁盘为存储介质的超大数（T以上量级）计算能力。