3

我正在使用基本的 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
4

3 回答 3

2

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

此外：

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

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

于 2013-05-02T22:35:15.657 回答
1

每个单独的乘法都会为最坏情况的输入分配足够的空间。为最坏的情况分配是正确的做法，因为通常在完成乘法之前，您无法确定结果是否有前导零！

为防止问题中冗余前导零的级联效应，请在执行乘法后检查前导零，并相应地减少长度。请注意，如果您的输入都没有任何前导零，则它们相乘的结果不应超过 1。但是，对于减法来说，情况并非如此（它显然可以生成任意数量的前导零！）。

于 2013-05-02T22:37:47.583 回答
-1

我想出了如何解决这个问题。程序需要修改如下：

final public static int 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--;
    }
    int xFirstDigit = 1;
    while( result[xFirstDigit] == 0 ) xFirstDigit++;
    if( xFirstDigit > 1 ){
        int ctDigits = result[0] - xFirstDigit + 1;
        for( int xDigit = 1; xDigit <= ctDigits; xDigit++ ) result[xDigit] = result[xDigit + xFirstDigit - 1];
        result[0] = ctDigits;
    }
    return result[0];
}
于 2013-05-20T21:27:04.987 回答