Bee*_*ope 8 c multiplication multiprecision
考虑您要计算64位和128位无符号数乘以结果的低128位,并且您可用的最大乘法是C类64位乘法,它需要两个64位无符号输入并返回结果的低64位.
需要多少次乘法？
当然你可以用8来做:将所有输入分解为32位块并使用64位乘法来进行4*2 = 8所需的全宽32*32-> 64乘法,但是可以做得更好？
当然,算法应该在乘法之上仅进行"合理"数量的加法或其他基本算术(我对重新发明乘法作为加法循环并因此声称"零"乘法的解决方案不感兴趣).
四,但它开始变得有点棘手.
让一个和b是要被乘号,并提供一个0和一个1为低和高32位一个分别和b 0,b 1,b 2,b 3是32位组b,从从低到高分别.
期望的结果是(a 0 + a 1 •2 32)的剩余部分•(b 0 + b 1 •2 32 + b 2 •2 64 + b 3 •2 96)模2 128.
我们可以改写为(a 0 + a 1 •2 32)•(b 0 + b 1 •2 32)+(a 0 + a 1 •2 32)•(b 2 •2 64 + b 3 •2 96)modulo 2 128.
后一个模2 128的余数可以计算为单个64位乘64位乘法(其结果隐含地乘以2 64).
然后可以使用精心实施的Karatsuba步骤通过三次乘法计算前一项.简单版本将涉及一个33位乘33位到66位的产品,这是不可用的,但有一个棘手的版本可以避免它:
z0 = a0 * b0
z2 = a1 * b1
z1 = abs(a0 - a1) * abs(b0 - b1) * sgn(a0 - a1) * sgn(b1 - b0) + z0 + z2
最后一行只包含一个乘法; 另外两个伪乘法只是条件否定.绝对差异和条件否定在纯C中实现很烦人,但它可以完成.