CODEWITHSUNDEEP
algorithmrecursionbigintegermultiplicationkaratsuba
Hussam Abedlatif
Hussam Abedlatif

Reputation: 141

Karatsuba algorithm

I keep getting these errors when I run my program, can anyone spot the mistake? I am not experienced with using recursion and I might have messed up base case. My testing consists of two numbers of the same length, and my goal is to multiply two Big numbers without using the built in class. The method add just takes in two strings which are numbers and adds them, I checked and it works no matter how big the numbers are.

Error NumberFormatException: For input string: "" Integer.parseInt(Integer.java:592)

public static String mu (String value1, String value2){

    int length1 = value1.length();
    int length2 = value2.length();

    //If one value has more digits than the other, add zeroes to the front...



    int temp1;
    int temp2;
    int multiply;

    if (length1==1 || length2 ==1){
        temp1 = Integer.parseInt(value1);
        temp2 = Integer.parseInt(value2);
        multiply = temp1*temp2;
        return multiply +"" ;
    }else if (length1 ==0 || length2 ==0){
        return "";
    }



        int firstHalf = length1/2;
        int secondHalf = length1 - firstHalf;

        String value1First = value1.substring(0, firstHalf);
        String value1Second = value1.substring(firstHalf, secondHalf);


        String value2First = value2.substring(0, firstHalf);
        String value2Second = value2.substring(firstHalf, secondHalf);

        String ac = mu (value1First, value2First);
        String ad = mu (value1First, value2Second);
        String bc = mu(value1Second, value2First);
        String bd = mu(value1Second, value2Second);

        String zeroesToAdd= null;
        String zeroesToAdd2 = null;
        for (int i=0; i<length1; i++){
            zeroesToAdd = "0"+ zeroesToAdd;
        }
        for (int i=0; i<length1/2; i++){
            zeroesToAdd2 = "0"+ zeroesToAdd2;
        }

        String firstPart = ac + zeroesToAdd;
        String secondPart = (add(ad,bc))+zeroesToAdd2;
        String thirdPart = bd;

        String add1 = add(firstPart, secondPart);
        String add2;




        return add(add1, thirdPart);
    }

Upvotes: 1

Views: 579

Answers (1)

arunk2
arunk2

Reputation: 2416

Error NumberFormatException: For input string: "" Integer.parseInt(Integer.java:592)

is caused by the code

Integer.parseInt(value1)  or
Integer.parseInt(value2)

You might want to try add more cases for combination of str lengths (1,1) (1,0) (0,1) (0,0). Following code might help!

if (length1==1 && length2 ==1){
    temp1 = Integer.parseInt(value1);
    temp2 = Integer.parseInt(value2);
    multiply = temp1*temp2;
    return multiply +"" ;
}else if (length1 ==0 && length2 ==0){
    return "";
}
else if (length1 ==0 && length2 ==1){
    return value2;
}
else if (length1 ==1 && length2 ==0){
    return value1;
}

Hope it helps!

Upvotes: 2

Related Questions