Алгоритм Карацубы без BigInteger в Java, неожиданное поведение при рекурсии

Итак, я хочу запустить алгоритм Карацубы без использования класса BigInteger в Java, поэтому, следуя псевдокоду и этот вопрос, я пришел со следующим кодом

public static long recKaratsuba(long i1, long i2){

        if(i1<10 || i2<10) {
            return i1*i2 ;
        }

        long len = Math.round(Long.toString(Math.max(i1,i2)).length());
        long N  = Math.round(len/2) ;


        long b = (long) (i1% Math.pow(10, N)) ;
        long a = (long) (i1/ Math.pow(10,N));
        long d = (long) (i2% Math.pow(10,N)) ;
        long c = (long) (i2/ Math.pow(10,N));

        //System.out.println("a,b,c,d :" + a + b + c + d);



        long ac = recKaratsuba(a, c) ;
        long bd = recKaratsuba(b, d) ;
        long pos = recKaratsuba(a+b,c+d) ;

        return ((long)(bd + ac*Math.pow(10,len) + (pos -ac -bd)*Math.pow(10,N) )) ;
    }

Теперь проблема в том, что он дает неправильный ответ: 1234 * 5678 дает 11686652, что должно было быть 7006652. Как новичок в Java и алгоритмах, я не могу точно определить точную ошибку в этом коде, также я понимаете, что эта программа очень неэффективна и не работает для более чем 4 цифр (согласно связанному вопрос). Но это интуитивно то, что я изначально придумал после изучения псевдокода.

Итак, мой вопрос: в чем проблема в моем коде и как выполнить следующий алгоритм без использования метода BigInteger?


java algorithm math karatsuba
person BrownBoi    schedule 23.07.2020    source источник
comment
Как отлаживать небольшие программы   -  person khelwood    schedule 23.07.2020

Ответы (1)


arrow_upward
2
arrow_downward

Я заметил несколько вещей:

  • Вместо i1 и i2 можно использовать x и y
  • Переменные len и N имеют тип int, а не long
  • Нет необходимости округлять максимальную длину строковых представлений: длины - это целые числа, целые числа - целые числа и не могут быть округлены
  • Нет необходимости округлять деление на 2: деление целого числа всегда приводит к целому числу (выполняется целочисленное деление)
  • Ошибка в операторе возврата: вместо Math.pow(10, len) должно быть Math.pow(10, 2 * N), это важно, если N неравномерно
  • Избегайте нескольких одинаковых вычислений: особенно Math.pow(10, N)



Фиксированный код дает правильные результаты для всех примеров, которые я тестировал.

    public static long recKaratsuba2(long x, long y) {
        if (x < 10 || y < 10) {
            return x * y;
        }

        int len = Long.toString(Math.max(x, y)).length();
        double den = Math.pow(10, len / 2);
        long a = (long) (x / den);
        long b = (long) (x % den);
        long c = (long) (y / den);
        long d = (long) (y % den);

        long ac = recKaratsuba2(a, c);
        long bd = recKaratsuba2(b, d);
        long pos = recKaratsuba2(a + b, c + d);

        return (long) (bd + den * (ac * den + (pos - ac - bd)));
    }
person Community    schedule 23.07.2020