递归 Karatsuba 乘法不起作用？

Question

我正在尝试通过递归调用实现 Karatsuba multiplication。下面的代码应该可以工作，但我总是得到错误的答案。有什么想法吗？

    public static long karatsuba(long x, long y){
        //base case:
        if (x < 10 || y < 10) return x * y;

        //length of digits:
        int xSize = String.valueOf(x).length();
        int ySize = String.valueOf(y).length();
        int N     = Math.max(xSize, ySize);

        //split each number in half (by length of digits):
        long numX_hi = Long.valueOf((String.valueOf(x).substring(0, N/2)));
        long numX_lo = Long.valueOf((String.valueOf(x).substring(N/2, xSize)));
        long numY_hi = Long.valueOf((String.valueOf(y).substring(0, N/2)));
        long numY_lo = Long.valueOf((String.valueOf(y).substring(N/2, ySize)));

        //solve multiplications recursively:
        long z0 = karatsuba(numX_lo,numY_lo);
        long z1 = karatsuba((numX_hi+numX_lo),(numY_hi+numY_lo));
        long z2 = karatsuba(numX_hi,numY_hi);

        //answer:
        return  (long)(z2 * Math.pow(10,N))  +  (long)((z1-z2-z0) * Math.pow(10,(N/2)))  +  (z0);
    }

这里有几个测试用例：

1) karatsuba(1234,5678) >>> 6952652

*应该是7006652

2) karatsuba(4589, 7831) >>> 34649459

*应该是35936459

3) karatsuba(911, 482) >>> 44722

*应该是472842

Answer 1

你的方法有两个明显的问题。

首先，您应该从最后一位（最低有效位）开始拆分，而不是从第一位开始。所以如果你有这两个数字：

1234
567890

您目前是这样拆分它们的：

123   4 (123*1000+4)
567 890 (567*1000+890)

这会让你得到错误的结果，因为 1234 != 123*1000+4

您应该像这样拆分它们：

  1 234  (1*1000+234)
567 890  (567*1000+890)

我发现的第二个错误发生在你把东西加回去的时候。

return  (long)(z2 * Math.pow(10,N))  +  (long)((z1-z2-z0) * Math.pow(10,(N/2)))  +  (z0);

return 奇数 N 的结果是否不正确，因为 N/2 将向上舍入，因此 N != ((N/2)*2)

我合并了两个修复程序，现在我得到了正确的结果：

public static long karatsuba(long x, long y){
    //base case:
    if (x < 10 || y < 10) return x * y;

    //length of digits:
    int xSize = String.valueOf(x).length();
    int ySize = String.valueOf(y).length();
    int halfN     = Math.max(xSize, ySize) / 2; // store N/2 instead of N
    int splitX = xSize - halfN;  // count the split point from xSize down
    int splitY = ySize - halfN;  // count the split point from ySize down

    //split each number in half (by length of digits):
    long numX_hi = Long.valueOf((String.valueOf(x).substring(0, splitX)));
    long numX_lo = Long.valueOf((String.valueOf(x).substring(splitX)));
    long numY_hi = Long.valueOf((String.valueOf(y).substring(0, splitY)));
    long numY_lo = Long.valueOf((String.valueOf(y).substring(splitY)));

    //solve multiplications recursively:
    long z0 = karatsuba(numX_lo,numY_lo);
    long z1 = karatsuba((numX_hi+numX_lo),(numY_hi+numY_lo));
    long z2 = karatsuba(numX_hi,numY_hi);

    //answer:
    return  (long)(z2 * Math.pow(10,halfN*2))  +  (long)((z1-z2-z0) * Math.pow(10,halfN))  +  (z0);
}

Answer 2

如果一个数字字符串的长度是另一个数字字符串的两倍以上，则接受的解决方案会给出 StringIndexOutOfBoundsException，因为 splitX 或 splitY 将为负数。为了防止这个问题，必须捕获这个异常，然后将 halfN 设置为 Math.min(xSize, ySize)/2 。这是更正后的代码：

public static long karatsuba(long x, long y){
    //base case:
    if (x < 10 || y < 10) return x * y;

    //length of digits:
    int xSize = String.valueOf(x).length();
    int ySize = String.valueOf(y).length();

    int halfN = Math.max(xSize, ySize) / 2; // store N/2 instead of N
    if (halfN >= xSize || halfN >= ySize){
        halfN = Math.min(xSize, ySize) / 2; // prevents string index error
    }
    int splitX = xSize - halfN;  // count the split point from xSize down
    int splitY = ySize - halfN;  // count the split point from ySize down

    //split each number in half (by length of digits):
    long numX_hi = Long.valueOf((String.valueOf(x).substring(0, splitX)));
    long numX_lo = Long.valueOf((String.valueOf(x).substring(splitX)));
    long numY_hi = Long.valueOf((String.valueOf(y).substring(0, splitY)));
    long numY_lo = Long.valueOf((String.valueOf(y).substring(splitY)));

    //solve multiplications recursively:
    long z0 = karatsuba(numX_lo,numY_lo);
    long z1 = karatsuba((numX_hi+numX_lo),(numY_hi+numY_lo));
    long z2 = karatsuba(numX_hi,numY_hi);

    //answer:
    return  (long)(z2 * Math.pow(10,halfN*2))  +  (long)((z1-z2-z0) * Math.pow(10,halfN))  +  (z0);
}

递归 Karatsuba 乘法不起作用？

Recursive Karatsuba multiplication not working?

java

algorithm

recursion