Как сравнить различные алгоритмы умножения в диапазоне чисел

Проходя лекцию MIT в MITOpencourseware (6.006 лекция 12), я наткнулся на упоминание о 4 алгоритмах умножения (для умножения двух n-значных чисел) -

  1. Обычный наивный подход со сложностью O(n^2)
  2. Алгоритм Карацубы - O (n ^ 1,584)
  3. Тум-Кук(Toom3) - O(n^1,465)
  4. Шёнхаге-Штрассена - O(nlog(n)log(log(n)))

Теперь нужно было выяснить, в каких пороговых точках (т. е. при значениях n) один метод превосходит другой как лучший алгоритм. Было упомянуто, что все вышеперечисленное находится в пакете gmpy.

Чтобы попробовать это, я обратился к документации пакета gmpy2 по следующей ссылке - https://gmpy2.readthedocs.io/en/latest/intro.html

Однако при беглом просмотре частей этой документации показалось, что gmpy2 больше подходит для работы с большими числами. В частности, я не нашел отдельных функций, реализующих каждый из этих 4 вышеперечисленных алгоритмов. Итак, существуют ли какие-либо части gmpy2, в которых реализованы эти алгоритмы, чтобы я мог построить график времени работы этих алгоритмов в зависимости от n (количества цифр)?


python multiplication gmpy strassen karatsuba
person Anirban Chakraborty    schedule 03.09.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я сопровождаю gmpy2.

gmpy2 не реализует напрямую какие-либо алгоритмы умножения. Он просто вызывает алгоритмы, реализованные в GMP.

Много лет назад я написал на чистом Python реализацию арифметики с множественной точностью. Он использует наивную, Карацубу, Toom-3, Toom-4 и свертку Нуссбаумера для умножения. (Интересно, что если вы выберете достаточно большую точность, чистое решение Python, которое рекурсивно вызывает Toom-4, Toom-3, Karatsuba, может быть быстрее, чем версия только Karatsuba, используемая в Python и написанная на C.) Несколько разных алгоритмов деления также реализуются.

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

Его можно найти по адресу DecInt.

person casevh    schedule 03.09.2020