递归Karatsuba乘法不起作用？

我正在尝试通过递归调用实现Karatsuba乘法 。 下面的代码应该可行，但我一直得到错误的答案。 有什么想法吗？

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); 

将返回奇数N s的错误结果，因为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); }