我正在编写需要快速乘大数的数学代码。它可以将一个整数数组与一个单独的整数相乘。在C++中，代码如下（对于无符号整数）：
void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) {
unsigned __int64 of = 0; // overflow
unsigned i = 0; // loop variable
while (i < len) {
of += (unsigned __int64)a[i] * b + r[i];
r[i] = (unsigned)of;
of >>= 32;
++i;
}
r[i] = (unsigned)of; // save overflow
}
我手动展开了这个循环，将其转换为64位，并对.asm编译器输出进行了进一步的优化。现在，主要的.asm循环看起来像这样：
mov rax, rdi ; rdi = b
mul QWORD PTR [rbx+r10*8-64] ; rdx:rax = a[i] * b; r10 = i
mov rsi, QWORD PTR [r14+r10*8-64] ; r14 = r; rsi = r[i]
add rax, rsi
adc rdx, 0
add rax, r11 ; r11 = of (low part)
adc rdx, 0
mov QWORD PTR [r14+r10*8-64], rax ; save result
mov r11, rdx
; this repeats itself 8 times with different offsets
当我对此进行基准测试时，在我的Core2 Quad上每次乘法平均需要约6.3个周期。
我的问题是：有没有什么方法可以加速这个过程？不幸的是，我看不出如何避免其中一个加法和乘法总是需要RDX:RAX，因此我需要移动数据而不能“并行乘法”。
有任何想法吗？
更新： 经过进一步测试，我已经成功将速度提升到每个64位MUL大约需要5.4个周期（包括所有的add、move和loop开销）。我想这可能是在Core2上最好的效果，因为Core2没有非常快的MUL指令：它的吞吐量为3，延迟为6（或7）个周期。Sandy Bridge将更好，吞吐量为1，延迟为3（或4）个周期。
关于GMP的较低数字：我从他们的源代码中得到了这个数字，我认为它是一个理论上的数字。但确切的是，这是为AMD K9 CPU计算出来的数字。从我所读到的内容中可以得知，AMD比（旧款）Intel芯片有一个更快的MUL单元。