Stack Overflow Asked by BrownBoi on December 23, 2021
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?
There are a few things i notice:
Math.pow(10, len)
should be Math.pow(10, 2 * N)
instead, this is important if N is unevenMath.pow(10, N)
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)));
}
Answered by user13984475 on December 23, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP