计算 64 位乘以 128 位乘积的低 128 位需要多少次 64 位乘法? [英] How many 64-bit multiplications are needed to calculate the low 128-bits of a 64-bit by 128-bit product?

问题描述

考虑到您要计算 64 位和 128 位无符号数相乘结果的低 128 位，并且您可用的最大乘法是类 C 的 64 位乘法，它需要两个64 位无符号输入并返回结果的低 64 位.

Consider that you want to calculate the low 128-bits of the result of multiplying a 64-bit and 128-bit unsigned number, and that the largest multiplication you have available is the C-like 64-bit multiplication which takes two 64-bit unsigned inputs and returns the low 64-bits of the result.

需要多少次乘法?

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

Certainly you can do it with eight: break all the inputs up into 32-bit chunks and use your 64-bit multiplication to do the 4 * 2 = 8 required full-width 32*32->64 multiplications, but can one do better?

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

Of course the algorithm should do only a "reasonable" number of additions or other basic arithmetic on top of the multiplications (I'm not interested in solutions that re-invent multiplication as an addition loop and hence claim "zero" multiplications).

推荐答案

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

Four, but it starts to get a little tricky.

设 a 和 b 是要相乘的数字，a₀ 和 a₁分别是a的低32位和高32位，b₀，b₁, b₂, b₃b 的 32 位组，分别从低到高.

Let a and b be the numbers to be multiplied, with a₀ and a₁ being the low and high 32 bits of a, respectively, and b₀, b₁, b₂, b₃ being 32-bit groups of b, from low to high respectively.

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

The desired result is the remainder of (a₀ + a₁•2³²) • (b₀ + b₁•2³² + b₂•2⁶⁴ + b₃•2⁹⁶) modulo 2¹²⁸.

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

We can rewrite that as (a₀ + a₁•2³²) • (b₀ + b₁•2³²) + (a₀ + a₁•2³²) • (b₂•2⁶⁴ + b₃•2⁹⁶) modulo 2¹²⁸.

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

The remainder of the latter term modulo 2¹²⁸ can be computed as a single 64-bit by 64-bit multiplication (whose result is implicitly multiplied by 2⁶⁴).

那么前一项可以用三个乘法计算仔细实施了Karatsuba 步骤.简单版本将涉及 33 位乘 33 位到 66 位产品，该产品不可用，但有一个更棘手的版本可以避免它:

Then the former term can be computed with three multiplications using a carefully implemented Karatsuba step. The simple version would involve a 33-bit by 33-bit to 66-bit product which is not available, but there is a trickier version that avoids it:

z0 = a0 * b0
z2 = a1 * b1
z1 = abs(a0 - a1) * abs(b0 - b1) * sgn(a0 - a1) * sgn(b1 - b0) + z0 + z2

最后一行只包含一个乘法；另外两个伪乘法只是条件否定.在纯 C 中实现绝对差和条件否定很烦人，但可以做到.

The last line contains only one multiplication; the other two pseudo-multiplications are just conditional negations. Absolute-difference and conditional-negate are annoying to implement in pure C, but it could be done.

这篇关于计算 64 位乘以 128 位乘积的低 128 位需要多少次 64 位乘法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！