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

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

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

<小时/>

这就是通常的做法。我的 BigIntegers Delphi 代码也做了同样的事情，IIRC 也是 Knuth 在他的《计算机编程艺术》(第二卷)中展示的算法。