您的方法有两个明显的问题。
首先,您应该从最后一个(最低有效)数字开始分割,而不是从第一个数字开始。所以如果你有这两个数字:
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);
Will return an incorrect result for odd N
s, as N/2
will be rounded up down and therefore 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);
}