英文:
Karatsuba Algorithm without BigInteger in Java, unexpected behaviour while recursion
问题
以下是翻译好的内容:
所以我想在Java中运行Karatsuba算法,而不使用BigInteger类,因此在遵循伪代码和这个问题后,我得到了以下代码:
public static long recKaratsuba(long i1, long i2){
if(i1 < 10 || i2 < 10) {
return i1 * i2;
}
long len = Math.round(Long.toString(Math.max(i1, i2)).length());
long N = Math.round(len / 2);
long b = (long) (i1 % Math.pow(10, N));
long a = (long) (i1 / Math.pow(10, N));
long d = (long) (i2 % Math.pow(10, N));
long c = (long) (i2 / Math.pow(10, N));
//System.out.println("a,b,c,d :" + a + b + c + d);
long ac = recKaratsuba(a, c);
long bd = recKaratsuba(b, d);
long pos = recKaratsuba(a + b, c + d);
return ((long) (bd + ac * Math.pow(10, len) + (pos - ac - bd) * Math.pow(10, N)));
}
现在,这段代码的问题在于它产生了错误的答案,1234 * 5678 得到的结果是 11686652,但实际上应该是 7006652。作为一个刚开始学习Java和算法的初学者,我无法准确找出代码中的错误。我也意识到这个程序非常低效,并且对于超过4位数的情况无法工作(根据链接的问题)。但这基本上是我在学习伪代码后最初想出的方法。
所以我的问题是,我的代码有什么问题,如何在不使用BigInteger方法的情况下执行这个算法?
英文:
So I want to run Karatsuba Algorithm without using class BigInteger in Java, so upon following the pseudo-code and this question, I came with the following code
public static long recKaratsuba(long i1, long i2){
if(i1<10 || i2<10) {
return i1*i2 ;
}
long len = Math.round(Long.toString(Math.max(i1,i2)).length());
long N = Math.round(len/2) ;
long b = (long) (i1% Math.pow(10, N)) ;
long a = (long) (i1/ Math.pow(10,N));
long d = (long) (i2% Math.pow(10,N)) ;
long c = (long) (i2/ Math.pow(10,N));
//System.out.println("a,b,c,d :" + a + b + c + d);
long ac = recKaratsuba(a, c) ;
long bd = recKaratsuba(b, d) ;
long pos = recKaratsuba(a+b,c+d) ;
return ((long)(bd + ac*Math.pow(10,len) + (pos -ac -bd)*Math.pow(10,N) )) ;
}
Now, the problem with this is that it's producing the wrong answer, 1234*5678 is giving 11686652, which should've been 7006652.
As a beginner to Java and algorithms, I am unable to pinpoint the exact bug in this code, also I do realize that this program is very inefficient and doesn't work for more than 4 digits (according to the linked question ). But this is intuitively what I came up with originally after learning the pseudo-code.
So my question is, what is the problem in my code and how do I execute the following algorithm without using the BigInteger method?
答案1
得分: 2
以下是您要翻译的内容:
有几件事情我注意到了:
- 可以考虑使用 x 和 y,而不是 i1 和 i2
- 变量 len 和 N 是整型,不是长整型
- 没有必要对字符串表示的长度取最大值四舍五入:长度是整数,整数是整数,不需要四舍五入
- 不需要对除以 2 进行四舍五入:整数相除的结果始终是整数(执行整数除法)
- 错误在于 return 语句:
Math.pow(10, len)
应改为Math.pow(10, 2 * N)
,如果 N 是奇数,这一点很重要 - 避免多次相同的计算:尤其是
Math.pow(10, N)
修正后的代码在我测试过的所有示例中都给出了正确的结果。
public static long recKaratsuba2(long x, long y) {
if (x < 10 || y < 10) {
return x * y;
}
int len = Long.toString(Math.max(x, y)).length();
double den = Math.pow(10, len / 2);
long a = (long) (x / den);
long b = (long) (x % den);
long c = (long) (y / den);
long d = (long) (y % den);
long ac = recKaratsuba2(a, c);
long bd = recKaratsuba2(b, d);
long pos = recKaratsuba2(a + b, c + d);
return (long) (bd + den * (ac * den + (pos - ac - bd)));
}
注意:由于您要求只返回翻译的内容,我已经移除了不属于翻译部分的说明性文字。如果您需要更多帮助,请随时提问。
英文:
There are a few things i notice:
- Instead of i1 and i2 maybe use x and y
- Variables len and N are int, not long
- No need to round the maximum of the lengths of the string-representations: Lengths are ints, ints are whole numbers and cant be rounded
- No need to round the division by 2: Dividing a whole number will always result in a whole number (integer division is done)
- The error is in the return-statement:
Math.pow(10, len)
should beMath.pow(10, 2 * N)
instead, this is important if N is uneven - Avoid multiple identical calculations: especially
Math.pow(10, N)
<br><br>
The fixed code gives the correct results for all examples that i have tested.
public static long recKaratsuba2(long x, long y) {
if (x < 10 || y < 10) {
return x * y;
}
int len = Long.toString(Math.max(x, y)).length();
double den = Math.pow(10, len / 2);
long a = (long) (x / den);
long b = (long) (x % den);
long c = (long) (y / den);
long d = (long) (y % den);
long ac = recKaratsuba2(a, c);
long bd = recKaratsuba2(b, d);
long pos = recKaratsuba2(a + b, c + d);
return (long) (bd + den * (ac * den + (pos - ac - bd)));
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论