关于大数核心运算(对于应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条指令，大体是这个样子。
mov eax, s1
mov edx, s2
mul edx
add ecx, eax
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= sum(s1[ i ]*s2, 0<= i< len1, 0 <= k-i<len2).
２.以行为主的乘法
若被乘数是s1[], 其长度是len1, 乘数是s2[], 其长度是len2
计算过程为,先固定k,0<=k<len2, n=s2, 计算p[ i+k ]=sum(s1[ i ]*n,0<= i< len1)
c语言版本的源程序。
//假定s_len总是32的倍数
uint64_t muladd_c (uint32_t *s1, int s1_len,uint32_t *s2)
{
int pass= s1_len/32;
uint64_t sum=0;
uint32_t *base;
for (int i=0;i<pass;i++)
{
base= s1 + (i*32);
for (int j=0;j<32;j++)
{
sum+= (uint64_t)base * (uint64_t)s2;
}
}
return sum;
}
写个椭圆曲线整数分解的吧
这个要待基础模块完成后，才能进行下一步。。。
为了方便开发测试，我先把 dll 导出框架搭好，测试 app 写好。
"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出函数的 ID 号；其中 @ 代表 1 或 2，对应于 bin 或 dec 内核
上图即为当前的测试 app 的截图，
相比之前的，功能更强大，扩展性更强，
其中 "Arbitrary-precision arithmetic" 区按函数入参类型分类，具有更灵活的扩展性
几乎所有的导出函数都可在此框架中得以测试。
当然，该界面只是做了些基本的对齐排版，
谈不上什么美学，可能会遭到一些吐槽，
限于个人能力，就由他去吧。。。
之前一些美妙的想法，已逐步实现，比如输出模式，有// 输出格式：进制模式
enum class basemode
{
smart, // 以最快的进制输出：当对象为十进制内核时，相当于 dec；否则，相当于 hex
bin, // 强制以二进制输出
oct, // 强制以八进制输出
dec, // 强制以十进制输出
hex, // 强制以16进制输出
huge, // 带空格换行符输出（default）：基于 smart，但更适合超长大数输出
};截图上的即为 huge 模式输出的：从末尾起向前，每十位成一块加一空格（也可指定为逗号,或撇号'）分隔；每十块将空格符替换成换行符，
这样的格式化输出，更利于阅读或存储。
// 输出格式：分隔符
enum class separator
{
none, // 不 用 分隔符
space, // 用空格分隔符（default）
accent, // 用撇号分隔符（单引号）
comma, // 用逗号分隔符
};
明天，我们要正式复工啦！
之前一直在家远程办公，抽空可以开发一下这个算法库，
通过阅读相关标准，再加上自己的实践，
很快掌握了相关知识，这就是最大的收获。
gxqcn 发表于 2020-3-29 12:06
为了方便开发测试，我先把 dll 导出框架搭好，测试 app 写好。
"Arbitrary-precision arithmetic" 中 [@xxx] 代表的是导出 ...
软件看起来不错，
不过我现在习惯了mathematica软件的方式，
代码能够粘贴很爽，
你的软件需要点鼠标给软件赋值（旧版本是这样，新版本不知道如何），
这点鼠标其实操作起来很麻烦的，
以前用你的软件的input窗口来过滤掉窗口里面的非数字，
现在我自己学会了正则表达式，你的软件对我来说没帮助了。
:b:期待新突破
gxqcn 发表于 2020-2-24 09:11
谢谢！非常感谢！这样，我对 x64 平台的性能有个预期目标了。
指令执行周期，64位乘法6周期，32位乘法5周期，这是基本指令差异，非常显著的了
64位相比32位，一次乘法可获得双倍的bit数，即便周期数是 6:5，实效则为 5:3，
64位系统还有：可用寄存器丰富，传参快等优点