Код Java-рекурсии умножения Карацубы не работает?

Прежде всего, я попытался взглянуть на ваш код, он заставляет программиста теряться, кое-что, прежде чем мы перейдем к решению.

Общий совет. Не рекомендуется преобразовывать строку в значение и обратно и вперед, как вы, это не работает так. Я также пытался отладить ваш код, это просто дьявольский круг.

Поэтому я бы начал с проверки длины значения и максимального значения.

Чем, если одно из значений меньше 2 длины, означает, что все, что меньше 10, выполняет умножение, в противном случае - алгоритм рекурсии Карацубы.

Вот решение:

public static long karatsuba(long num1, long num2) {

    int m = Math.max(
            String.valueOf(num1).length(),
            String.valueOf(num2).length()
    );

    if (m < 2)
        return num1 * num2;

    m = (m / 2) + (m % 2);

    long b = num1 >> m;
    long a = num1 - (b << m);
    long d = num2 >> m;
    long c = num2 - (d << m);

    long ac = karatsuba(a, c);
    long bd = karatsuba(b, d);
    long abcd = karatsuba(a + b, c + d);

    return ac + (abcd - ac - bd << m) + (bd << 2 * m);
}

Некоторый тест;

public static void main(String[] args) {
    System.out.println(karatsuba(1, 9));
    System.out.println(karatsuba(1234, 5678));
    System.out.println(karatsuba(12345, 6789));
}

Результат будет

9
7006652
83810205

Это меньше боли, чем ваш код Stringish. Кстати, решение взято из pesudo в вики и этого класс.

Интересный алгоритм. Одна ошибка в

return String.valueOf(((int)Math.pow(10, first.length()))*(Long.parseLong(a)) + (((int)Math.pow(10, first.length()/2))*Long.parseLong(d)) + (Long.parseLong(c)));

В конце должно быть Long.parseLong(b) вместо Long.parseLong(c).

А при промежуточных вычислениях может случиться так, что две строки будут разной длины. Это тоже работает не корректно.

Пожалуйста, разрешите некоторые комментарии для улучшения реализации. Идея использовать строки, кажется, позволяет использовать большие числа, но затем вы вводите такие вещи, как Long.parseLong() или (int)Math.pow(10, first.length()), ограничивая вас диапазоном long или int.

Если вы действительно хотите делать большие числа, напишите свое собственное сложение на основе строк и умножение в десятой степени (это тривиально, добавляя несколько нулей).

И старайтесь избегать таких имен, как a, b, c или d — слишком легко забыть, что они означают, как и ваша первоначальная ошибка. Например. имена из Википедии немного лучше (с использованием z0, z1 и z2), но все же не идеально...