Рекурсивный алгоритм Карацубы, дающий неточные ответы - PullRequest
Новая
       61

Рекурсивный алгоритм Карацубы, дающий неточные ответы

1 голос
/ 26 мая 2020

Я пытался реализовать алгоритм умножения Карацубы на C ++ для двух больших чисел одинаковой длины. Мой код работает правильно для меньших чисел, например 3456 * 1492, но не работает с большими числами, такими как 64-значные. Как правило, первые несколько цифр отображаются правильно, но после этого возникают ошибки. Я использую библиотеку Boost multiprecision для обработки больших целых чисел.

Мой код выглядит следующим образом: 

cpp_int karatsuba(cpp_int n1, cpp_int n2) {
    if (n1 < 10 || n2 < 10) {
        return n1 * n2;
    }

    int len = countDigits(n1);

    cpp_int a = n1 / cpp_int(pow(10, len/2));
    cpp_int b = n1 % cpp_int(pow(10, len/2));
    cpp_int c = n2 / cpp_int(pow(10, len/2));
    cpp_int d = n2 % cpp_int(pow(10, len/2));

    cpp_int sub1 = karatsuba(a, c);
    cpp_int sub2 = karatsuba(b, d);
    cpp_int sub3 = karatsuba(a+b, c+d) - sub1 - sub2;

    return sub1 * cpp_int(pow(10, len)) + sub3 * cpp_int(pow(10, len/2)) + sub2;
}

Я сравнил свой код с несколькими реализациями в Интернете и не смог найти никаких существенных различий, которые могли бы повлиять на ответ. Возможно, есть проблема с точностью типа cpp_int или проблема в моем коде?

Большое спасибо за вашу помощь!

1 Ответ

2 голосов
/ 26 мая 2020

Я подозреваю, что одна проблема заключается в том, что pow возвращает представление с плавающей запятой, которое неточно конвертируется в cpp_int.

Использование многопрецизионной версии pow может помочь. 2 округления вниз, поэтому при вычислении pow (10, len) это должно быть pow (10, (len / 2) * 2).

...