递归Karatsuba乘法不起作用? [英] Recursive Karatsuba multiplication not working?
问题描述
我正在尝试通过递归调用实现 Karatsuba乘法.下面的代码应该可以工作,但是我总是得到错误的答案.有什么想法吗?
I'm trying to implement Karatsuba multiplication through recursive calls. The code below should work, but I keep getting the wrong answer. Any thoughts?
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
1) karatsuba(1234,5678) >>> 6952652
*应该为 7006652
2)karatsuba(4589,7831)>>> 34649459
2) karatsuba(4589, 7831) >>> 34649459
*应为 35936459
3)karatsuba(911,482)>>> 44722
3) karatsuba(911, 482) >>> 44722
*应该为 472842
推荐答案
您的方法有两个明显的问题.
There are two distinct problems with your method.
首先,您应该从最后一位(最低有效数字)开始而不是第一位进行分割.因此,如果您有以下两个数字:
Firstly, you should split starting from the last (least significant) digit, not the first. So if you've got these two numbers:
1234
567890
您当前按如下方式拆分它们:
You currently split them like this:
123 4 (123*1000+4)
567 890 (567*1000+890)
这会为您带来错误的结果,因为1234 != 123*1000+4
This gets you the wrong result because 1234 != 123*1000+4
您应该像这样拆分它们:
You should instead split them like this:
1 234 (1*1000+234)
567 890 (567*1000+890)
我发现的第二个错误发生在将事物重新添加在一起时.
The second error I discovered happens when you add things back together.
return (long)(z2 * Math.pow(10,N)) + (long)((z1-z2-z0) * Math.pow(10,(N/2))) + (z0);
对于奇数的N
,将返回错误的结果,因为N/2
会四舍五入为向上,因此为N != ((N/2)*2)
Will return an incorrect result for odd N
s, as N/2
will be rounded up down and therefore N != ((N/2)*2)
我将这两个修复程序结合在一起,现在我得到了正确的结果:
I've combined the two fixes and now I get the correct results:
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);
}
这篇关于递归Karatsuba乘法不起作用?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!