Понимание алгоритма Шёнхаге-Штрассена (умножение огромных чисел)

Question

Мне нужно умножить несколько длинных чисел на 1000 с максимально эффективно в Python. Числа читаются из файла.

Я пытаюсь реализовать алгоритм Schönhage-Strassen для целочисленного умножения, но я застрял в понимании его определения и математики, особенно быстрого преобразования Фурье.

Любая помощь в понимании этого алгоритма, например, практический пример или псевдокод, будет принята с благодарностью.

Answer 1

Глава 4.3.3 Кнута TAOCP описывает его, а также содержит псевдокод FFT в других главах, которые могут использоваться для этого.

Answer 2

Не изобретай велосипед. GMP имеет отличную высокопроизводительную реализацию этого алгоритма, и любой алгоритм, написанный на чистом Python, будет как минимум в 100 раз медленнее, просто потому, что Python является интерпретируемым языком. Используйте gmpy , чтобы вызвать GMP из вашего приложения Python. Мне также любопытно, в каком приложении вы работаете, для которого требуется умножение таких больших чисел - возможно, существует более простой способ решения вашей проблемы.

Кроме того, как уже упоминалось в других ответах, «длина в несколько тысяч раз» недостаточно длинна, чтобы оправдать Шенхаге-Штрассен (вам нужно было бы не менее 10000 десятичных знаков, возможно, больше). Некоторые варианты Toom-Cook, такие как Toom-3, обычно используются в этом диапазоне. Опять же, не пишите это самостоятельно на Python - реализация GMP очень тщательно оптимизирована.

Answer 3

1000 цифр - это «маленький» для Schönhage-Strassen, который действительно стоит использовать. Вы можете взглянуть на умножение Toom Cook . gmpy - это оболочка Python для gmp, предоставляющая эти функции.