Мне нужно умножить несколько целых чисел с цифрами 1000s как можно более эффективно в Python. Номера читаются из файла.
Понимание алгоритма Шенхаге-Штрассена (огромное целочисленное умножение)
Ответ 1
Глава 4.3.3 из Knuth TAOCP описывает его, а также имеет некоторый псевдокод FFT в других главах, которые могут быть использованы для этого.
Ответ 2
1000 цифр - это "маленький" для Schönhage-Strassen, который действительно стоит использовать. Вы можете взглянуть на Toom Cook умножение. gmpy - это оболочка Python для gmp, предоставляющая эти функции.
Ответ 3
Не изобретайте велосипед. GMP имеет превосходную высокоэффективную реализацию этого алгоритма, и любой алгоритм, написанный на чистом Python, будет по меньшей мере в 100 раз медленнее, просто потому, что Python является интерпретированным языком. Используйте gmpy для вызова GMP из приложения Python. Мне также интересно, какое приложение, над которым вы работаете, требует умножения таких больших чисел - может быть более простой способ справиться с вашей проблемой.
Кроме того, как упоминалось в других ответах, "несколько тысяч цифр в длину" недостаточно длинны, чтобы оправдать Шенхаге-Штрассен (у вас должно быть не менее 10000 десятичных цифр, возможно, больше). В этом диапазоне обычно используется некоторый вариант Toom-Cook, такой как Toom-3. Опять же, не пишите это сами в Python - реализация GMP очень тщательно оптимизирована.