Karatsuba multiplication not working recursively with BigInteger

192 views Asked by At

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.

0

There are 0 answers