Search code examples
javaalgorithmkaratsuba

Karatsuba multiplication in Java

I am trying to do the Karatsuba multiplication here. The below code works for numbers with two digits (eg 78 * 34) but gives wrong results for numbers with digits greater than 2 (eg 5678 * 1234). I have attached the debugging logs. After a certain point the calculations are wrong. Can someone take a look and tell me if my understanding of the algorithm is incorrect?

static BigInteger karatsuba(BigInteger no1, BigInteger no2){
    BigInteger result = null;
    
    //Both numbers less than 10
    if(no1.compareTo(new BigInteger("9")) != 1 && no2.compareTo(new BigInteger("9")) != 1 ){
        return no1.multiply(no2);
    }
    
    String str1 = no1.toString();
    String str2 = no2.toString();
            
    if(str1.length() ==1) {
        str1 = "0" + str1;
    }
    if(str2.length() ==1) {
        str2 = "0" + str2;
    }
    
    int m = str1.length()/2;
    String a = str1.substring(0,m);
    String b = str1.substring(m,str1.length()); 
    
    m = str2.length()/2;
    String c = str2.substring(0,m);
    String d = str2.substring(m,str2.length());
    
    BigInteger step1 = karatsuba(new BigInteger(a),new BigInteger(c)); 
    BigInteger step2 = karatsuba(new BigInteger(b),new BigInteger(d)); 
    BigInteger step3 = karatsuba(new BigInteger(a).add(new BigInteger(b)),new BigInteger(d).add(new BigInteger(c)));
    BigInteger step4 = step3.subtract(step2).subtract(step1);
    
    int n = str1.length() > str2.length() ? str1.length() : str2.length();
    
    double db = Math.pow(10,n);
    double dbby2 = Math.pow(10,(n/2));
    
    step1 = step1.multiply(BigDecimal.valueOf(db).toBigInteger());
    step4 = step4.multiply(BigDecimal.valueOf(dbby2).toBigInteger());
    
    result = step1.add(step4).add(step2);
    return result;
}

Debug Logs:

After getting the result of 2652, the next calculations are wrong.

enter image description here

Solution

  • an obvious mistake is, that the multipliers are incorrectly padded with zeros

    if ((str1.length() & 1) == 1) {
    str1 = "0" + str1;
}
while (str2.length() < str1.length()) {
    str2 = "0" + str2;
}

    and here is the 2nd mistake:
    rounding error in the exponent because of the wrong     pow function

    step1 = step1.multiply(BigInteger.valueOf(10L).pow(n));
step4 = step4.multiply(BigInteger.valueOf(10L).pow(n/2));

    5678 * 1234 = 7006652
    84232332233 * 1532664392 = 129099896268632947336
    before padding with zeros: the length of str1 must always be greater than or equal to the length of str2