Алгоритм Карацубы

Я продолжаю получать эти ошибки, когда запускаю свою программу, может ли кто-нибудь заметить ошибку? У меня нет опыта использования рекурсии, и я мог ошибиться в базовом случае. Мое тестирование состоит из двух чисел одинаковой длины, и моя цель — умножить два больших числа без использования встроенного класса. Метод add просто принимает две строки, которые являются числами, и добавляет их, я проверил, и он работает независимо от того, насколько велики числа.

Ошибка NumberFormatException: для входной строки: "" 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);
    }

recursion algorithm multiplication biginteger karatsuba
person Hussam Abedlatif    schedule 03.07.2017    source источник
comment
Я продолжаю получать эти ошибки — абсолютно бесполезное описание проблемы. Какие ошибки вы получаете конкретно?   -  person Ken White    schedule 03.07.2017
comment
Исключение в основном потоке java.lang.NumberFormatException: для входной строки: в java.lang.NumberFormatException.forInputString(NumberFormatException.java:65) в java.lang.Integer.parseInt(Integer.java:592) в java.lang.Integer .parseInt(Integer.java:615) в main.mu(main.java:139) в main.mu(main.java:159) в main.main(main.java:304)   -  person Hussam Abedlatif    schedule 03.07.2017
comment
Если одна из длин равна 1, вы никогда не достигнете части, которая проверяет длину 0. Сначала сделайте эту проверку и верните пустую строку. Тогда в остальной части кода вы больше никогда не встретите длину 0. Конечно, вы также можете использовать BigInteger напрямую. Это использует Карацубу для больших значений (и даже более сложный код, такой как Toom-Cook 3, для еще больших значений).   -  person Rudy Velthuis    schedule 03.07.2017

Ответы (1)


arrow_upward
2
arrow_downward

Ошибка NumberFormatException: для входной строки: "" Integer.parseInt(Integer.java:592)

вызвано кодом

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

Возможно, вы захотите попробовать добавить больше случаев для комбинации длин строк (1,1) (1,0) (0,1) (0,0). Следующий код может помочь!

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;
}

Надеюсь, поможет!

person arunk2    schedule 03.07.2017
comment
если одно значение пустое, а другое имеет длину один, вернуть другое: зачем интерпретировать пустую строку не как ноль, а как единицу? - person greybeard; 21.07.2019