I am trying to multiply n digit number using karatsuba multiplication.
I am getting output for single digit number (Example 4 and 5 = 20).
But, when I multiply 1234 and 5678 I am getting error and no output result.
I have updated the code and error message. Please check.
The error is Click here
import java.math.BigInteger;
class karatsubamultiplication{
public static BigInteger karat(BigInteger number1, BigInteger number2){
if(number1.bitLength() < 4 && number2.bitLength() < 4)
return number1.multiply(number2);
//Finding maximum length of two
//int m = Math.max(number1, number2);
String first = number1.toString();
String second = number2.toString();
BigInteger a = new BigInteger(first.substring(0, first.length()/2));
BigInteger b = new BigInteger(first.substring(first.length() - first.length()/2, first.length()));
BigInteger c = new BigInteger(second.substring(0, second.length()/2));
BigInteger d = new BigInteger(second.substring(second.length() - second.length()/2, second.length()));
BigInteger ac = karat(a, c);
BigInteger bd = karat(b, d);
BigInteger abcd = karat(a.add(b), c.add(d));
BigInteger z = abcd.subtract(ac.add(bd));
int m = String.valueOf(number1).length();
BigInteger len = new BigInteger(String.valueOf(Math.pow(10, m)));
return (ac.multiply(len)).add(z.multiply(len.divide(BigInteger.valueOf(2)))).add(bd);
}
public static void main(String[] args){
BigInteger result = new BigInteger("0");
BigInteger x = new BigInteger("1234");
BigInteger y = new BigInteger("5678");
result = karat(x, y);
System.out.println(result);
}
}
Please correct the code. I have not checked whether two numbers are equal or not and length is odd or even.
Thank you.