重启大整数库 HugeCalc 的研发工作

liangbch

关于大数核心运算(对于应GMP的mpn目录下的底层函数)的进制。我仍然认为我的设计是最好的。
即32位下使用$2^30$进制,64位下使用$2^60$(其实单从大数乘法上看，$2^62$更好，但60的因数众多，更好拆分)进制。
非满进制格式的大数，存储开销稍大些，但可实现以列为主的乘法，可对双倍精度的乘积做多次累加而不溢出。
而满进制格式的大数，只能实现以行为主的大数乘法，无法充分利用SIMD指令的优势。

一个精心设计的乘法结构可充分利用SIMD的优势，加速大数运算的速度。
若每条指令的执行时间相当，则使用AVX512指令的$2^30$进制的大数乘法，极有可能比GMP64位的版本更快。

分析
一次64位×64位的乘法，等价于4次32位×32位的乘法. 故若4个32位×32位的乘法的实现快于一个64位×64位的乘法，则32位版本的乘法可快于64位乘法。
最近完成一个示范程序，核心是做s = sum( a[ i ] * b[ j ]),实现了４个版本，包括c语言版，sse2版, avx2版,avx512版, 计算4096对儿uint32乘法的积的累加，不考虑溢出，用时为6.3至0.25微秒。

|C版本|sse2|avx2|avx512|
|6.3us|0.92us|0.41us|0.25us|

下面比较一下各个版本的执行的指令数
对说32位C版本，典型的需要5条指令，大体是这个样子。

1. 
   
2. mov eax, s1
   
3. mov edx, s2
   
4. mul edx
   
5. add ecx, eax
   
6. add ebx, edx
   

复制代码

而我写的SSE2版本，每4次uint32乘uint32需要9条指令,平均每次乘法需要2.25条指令
AVX2版本，每8次uint32乘uint32需要7条指令，平均每次乘法需要0.88条指令。
AVX512版本，每16次uint32乘uint32需要7条指令，平均每次乘法需要0.44条指令。

附以列为主的乘法和以行为主的乘法
１.以列为主的乘法
若被乘数是s1[], 其长度是len1, 乘数是s2[], 其长度是len2
该算法计算过程为,先固定k,则p[k]= sum(s1[ i ]*s2[k-i], 0<= i< len1, 0 <= k-i<len2).

２.以行为主的乘法
若被乘数是s1[], 其长度是len1, 乘数是s2[], 其长度是len2
计算过程为,先固定k,0<=k<len2, n=s2[k], 计算p[ i+k ]=sum(s1[ i ]*n,0<= i< len1)

liangbch

c语言版本的源程序。

1. //假定s_len总是32的倍数
   
2. uint64_t muladd_c (uint32_t *s1, int s1_len,  uint32_t *s2)
   
3. {
   
4.    int pass= s1_len/32;
   
5.    uint64_t sum=0;
   
6.    uint32_t *base;
   
7. 
   
8.    for (int i=0;i<pass;i++)
   
9.    {
   
10.         base= s1 + (i*32);
    
11.         for (int j=0;j<32;j++)
    
12.         {
    
13.              sum+= (uint64_t)base[j] * (uint64_t)s2[i];       
    
14.         }       
    
15.    }
    
16.    return sum;   
    
17. }
    
18. 
    

复制代码

mathematica

写个椭圆曲线整数分解的吧

gxqcn

这个要待基础模块完成后，才能进行下一步。。。

gxqcn

为了方便开发测试，我先把 dll 导出框架搭好，测试 app 写好。

hugecalc v9.0

"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出函数的 ID 号；其中 @ 代表 1 或 2，对应于 bin 或 dec 内核

上图即为当前的测试 app 的截图，
相比之前的，功能更强大，扩展性更强，
其中 "Arbitrary-precision arithmetic" 区按函数入参类型分类，具有更灵活的扩展性
几乎所有的导出函数都可在此框架中得以测试。

当然，该界面只是做了些基本的对齐排版，
谈不上什么美学，可能会遭到一些吐槽，
限于个人能力，就由他去吧。。。


之前一些美妙的想法，已逐步实现，比如输出模式，有

1. // 输出格式：进制模式
   
2. enum class basemode
   
3. {
   
4.     smart,          // 以最快的进制输出：当对象为十进制内核时，相当于 dec；否则，相当于 hex
   
5.     bin,            // 强制以二进制输出
   
6.     oct,            // 强制以八进制输出
   
7.     dec,            // 强制以十进制输出
   
8.     hex,            // 强制以16进制输出
   
9.     huge,           // 带空格换行符输出（default）：基于 smart，但更适合超长大数输出
   
10. };

复制代码

截图上的即为 huge 模式输出的：从末尾起向前，每十位成一块加一空格（也可指定为逗号,或撇号'）分隔；每十块将空格符替换成换行符，
这样的格式化输出，更利于阅读或存储。

1. // 输出格式：分隔符
   
2. enum class separator
   
3. {
   
4.     none,           // 不 用 分隔符
   
5.     space,          // 用空格分隔符（default）
   
6.     accent,         // 用撇号分隔符（单引号）
   
7.     comma,          // 用逗号分隔符
   
8. };

复制代码

gxqcn

明天，我们要正式复工啦！

之前一直在家远程办公，抽空可以开发一下这个算法库，
通过阅读相关标准，再加上自己的实践，
很快掌握了相关知识，这就是最大的收获。

mathematica

gxqcn 发表于 2020-3-29 12:06
为了方便开发测试，我先把 dll 导出框架搭好，测试 app 写好。

"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出 ...

软件看起来不错，

不过我现在习惯了mathematica软件的方式，
代码能够粘贴很爽，
你的软件需要点鼠标给软件赋值（旧版本是这样，新版本不知道如何），
这点鼠标其实操作起来很麻烦的，

以前用你的软件的input窗口来过滤掉窗口里面的非数字，
现在我自己学会了正则表达式，你的软件对我来说没帮助了。

G-Spider

期待新突破

无心人

gxqcn 发表于 2020-2-24 09:11
谢谢！非常感谢！这样，我对 x64 平台的性能有个预期目标了。

指令执行周期，64位乘法6周期，32位乘法5周期，这是基本指令差异，非常显著的了

gxqcn

64位相比32位，一次乘法可获得双倍的bit数，即便周期数是 6:5，实效则为 5:3，
64位系统还有：可用寄存器丰富，传参快等优点