java - 任意精度乘法，Knuth 4.3.1 前导零消除

Question

我正在使用基本的 Knuth 4.3.1 算法 M 对自然数进行任意精度乘法。我在 Java 中的实现如下。问题在于它正在生成前导零，这似乎是算法不知道给定结果是否有两个位置或一个位置的副作用。例如，2 x 3 = 6(一位数)，但 4 x 7 = 28(两位数)。该算法似乎总是保留导致前导零的两位数。

我的问题有两个方面:(1) 我的算法是 M 的正确实现，还是我做错了什么不必要地创建前导零，以及 (2) 如果它是 M 的一个不可避免的副作用，它产生前导零，那么我们如何调整或使用改进的算法来避免前导零。

// Knuth M algorithm 4.3.1
final public static void multiplyDecimals( int[] decimalM1, int[] decimalN1, int[] result, int radix ){
    Arrays.fill( result, 0 );
    int lenM = decimalM1[0];
    int lenN = decimalN1[0];
    result[0] = lenM + lenN; 
    int iStepM = lenM;
    while( iStepM > 0 ){
        int iStepN = lenN;
        int iCarry = 0;
        while( iStepN > 0 ){
            int iPartial = decimalM1[iStepM] * decimalN1[iStepN] + result[iStepM + iStepN] + iCarry;
            result[iStepM + iStepN] = iPartial % radix;
            iCarry = iPartial / radix;
            iStepN--;
        }
        result[iStepM] = iCarry;
        iStepM--;
    }
    return;
}

算法的输出显示正在生成的阶乘，其中显示前导零。

1 01
2 002
3 0006
4 00024
5 000120
6 0000720
7 00005040
8 000040320
9 0000362880
10 000003628800
11 00000039916800
12 0000000479001600
13 000000006227020800
14 00000000087178291200
15 0000000001307674368000
16 000000000020922789888000
17 00000000000355687428096000
18 0000000000006402373705728000
19 000000000000121645100408832000
20 00000000000002432902008176640000

Answer 1

该算法根本不分配任何前导零。你是。您正在提供输出数组，并用零填充它。 Knuth 算法 M 不这样做。

另外:

1. 您当然应该跳过两个数字中的所有前导零。这会对性能产生巨大影响，因为它是一种 O(MN) 算法。最后的 M 和 N 之和几乎就是正确的输出位数；乘法后的最后一步是删除可能的前导零。

2. 如果当前 M 数字为零，您也可以跳过内部循环。这是 Knuth 的步骤 M2。请注意，数字零在自然界中出现的频率比 1/10 高:有一条关于此的定律表明每个数字 1、2、3、5、6、7、8、9 依次出现的可能性越来越小。