c - 计算 64 位乘 128 位乘积的低 128 位需要多少次 64 位乘法？

Question

假设您想计算 64 位和 128 位无符号数相乘结果的低 128 位，并且您可用的最大乘法是类 C 语言的 64 位乘法，它需要两个64 位无符号输入并返回结果的低 64 位。

需要多少次乘法？

当然你可以用八个来完成:将所有输入分成 32 位 block 并使用你的 64 位乘法来做 4 * 2 = 8 所需的全角 32*32->64 乘法，但可以一个做得更好？

当然，该算法应该仅在乘法之上进行“合理”数量的加法或其他基本算术(我对将乘法重新发明为加法循环并因此声称“零”乘法的解决方案不感兴趣).

Answer 1

四个，但它开始变得有点棘手。

令a和b为要相乘的数，a₀和a ₁分别为a的低32位和高32位，b₀，< em>b₁, b₂, b₃ 是b的32位组，分别从低到高。

期望的结果是 (a₀ + a₁•2^{32 的余数}) • (b₀ + b₁•2³² + b₂•2⁶⁴ + b₃•2⁹⁶ ) 模 2¹²⁸。

我们可以将其重写为 (a₀ + a₁•2³²) • (b₀ + b₁•2³²) +(a₀ + a₁•2³²) • ( b₂•2⁶⁴ + b₃•2⁹⁶ ) 模 2¹²⁸。

后一项模 2¹²⁸ 的余数可以计算为单个 64 位乘以 64 位乘法(其结果隐式乘以 2⁶⁴) .

然后前一项可以通过使用 a 的三个乘法来计算精心实现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 中实现起来很烦人，但可以做到。