BigInteger'dultilyToLen'函数的解释

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;

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

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的下一个更高整数对的进位。

其他循环几乎相同，但是它们必须将结果添加到已存储在z数组中的整数，因此它们不像第一个那样简单。

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

---

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