BigInteger 'multiplyToLen' 函数说明

Question

在我自己的大整数实现上工作时，我查看了 Java 的 BigInteger 源代码以进一步了解乘法算法，并主要关注 multiplyToLen()。

总的来说，函数好像是一般的小学乘法算法，但是关键部分看不懂。

首先，算法执行第一个循环，其中 x 和 y 是相乘的两个数字，z 是乘积：

int xstart = xlen - 1;
int ystart = ylen - 1;

...

for (int j=ystart, k=ystart+1+xstart; j >= 0; j--, k--) {
    long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK) + carry;
    z[k] = (int)product;
    carry = product >>> 32;
}

z[xstart] = (int)carry;

然后，进入下一个循环，这似乎更接近小学算法。

for (int i = xstart-1; i >= 0; i--) {
    carry = 0;
    for (int j=ystart, k=ystart+1+i; j >= 0; j--, k--) {
        long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK) +
                               (z[k] & LONG_MASK) + carry;
        z[k] = (int)product;
        carry = product >>> 32;
    }

    z[i] = (int)carry;
}

我已经尝试使用十进制数跟踪两个循环，但都无济于事，而且我无法掌握第一个循环与第二个循环的功能。

第一个循环中执行了乘法算法的哪一部分？

Answer 1

第一个循环将两个整数相乘（分别来自每个 BigInteger x 和 y）然后存储结果的低 32 位结果数组 z。较高的 32 位用作来自 x 和 y resp.

的下一对较高整数的进位

其他循环几乎一样，但是它们必须将结果添加到已经存储在z数组中的整数中，所以它们并不那么简单作为第一个。

摆弄 long 和 LONG_MASK 的位只是为了将整数视为 无符号 32 位值（Java 通常不知道无符号整数），方法是将它们提升为 64 位整数，然后屏蔽低 32 位以获得无符号的 32 位值。 64 位乘法结果忽略第 63 位中的任何溢出。低位存储（loop 1）或添加（other loops）到已经先前循环的计算结果，在 z 中找到。前 32 位用作下一次迭代的进位。

一般都是这样的。我的 Delphi BigIntegers 代码和 IIRC 一样，这也是 Knuth 在他的计算机编程艺术（第二卷）中展示的算法。

BigInteger 'multiplyToLen' 函数说明

Explanation of BigInteger 'multiplyToLen' Function

java

biginteger