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

Question

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

Я пытаюсь реализовать Шёнхаге-Штрассен алгоритм целочисленного умножения, но я застрял в понимании определения и математики, лежащей в его основе, особенно быстрого преобразования Фурье.

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

Answer 1

Глава 4.3.3 книги Кнута ТАОКП описывает это, а также в других главах есть псевдокод БПФ, который можно использовать для этого.

Answer 2

1000 цифр — это «мало» для Шёнхаге-Штрассена, поэтому его действительно стоит использовать.Вы можете взглянуть на Тум Кук умножение. gmpy — это оболочка Python для gmp, предоставляющая эти функции.

Answer 3

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

Кроме того, как упоминалось в других ответах, «длиной в несколько тысяч цифр» недостаточно, чтобы оправдать Шёнхаге-Штрассен (вам нужно иметь как минимум 10 000 десятичных цифр, а возможно, и больше).В этом диапазоне обычно используется какой-то вариант Тум-Кука, например Тум-3.Опять же, не пишите это самостоятельно на Python — реализация GMP очень тщательно оптимизирована.