#python #multiplication #karatsuba #gmpy #strassen
#python #умножение #карацуба #gmpy #strassen
Вопрос:
Проходя лекцию MIT в MITOpencourseware (6.006 лекция 12), я наткнулся на упоминание о 4 алгоритмах умножения (для умножения двух n-значных чисел) —
- Обычный наивный подход со сложностью O (n ^ 2)
- Алгоритм Карацубы — O(n ^ 1.584)
- Toom-Cook(Toom3) — O (n ^ 1.465)
- Schonhage-Strassen — O(nlog(n)log(log(n)))
Теперь нужно исследовать, в каких пороговых точках (т. Е. Значениях n) Один метод превзошел другой в качестве лучшего алгоритма. Упоминалось, что все вышеперечисленное находится в пакете gmpy.
Чтобы попробовать это, я обратился к документации пакета gmpy2 по следующей ссылке — https://gmpy2.readthedocs.io/en/latest/intro.html
Однако, просматривая части этой документации, казалось, что gmpy2 больше подходит для работы с большими числами. В частности, я не нашел отдельных функций, реализующих каждый из этих 4 алгоритмов. Итак, есть ли какие-либо части gmpy2, где реализованы эти алгоритмы, чтобы я мог построить график времени выполнения этих алгоритмов в отношении n (количество цифр)?
Ответ №1:
Я сопровождающий gmpy2.
gmpy2 напрямую не реализует никаких алгоритмов умножения. Он просто вызывает алгоритмы, реализованные в GMP
Много лет назад я написал чистую реализацию Python арифметики с множественной точностью. Для умножения используются свертки naive, Karatsuba, Toom-3, Toom-4 и Nussbaumer. (Интересно, что если вы выберете достаточно большую точность, решение на чистом Python, которое рекурсивно вызывает Toom-4, Toom-3, Karatsuba, может быть быстрее, чем версия Karatsuba only, используемая в Python и написанная на C.) Также реализована пара разных алгоритмов деления.
Легко модифицировать код и добавить глобальную переменную, чтобы подсчитать, сколько раз выполняется каждый шаг.
Его можно найти в DecInt