Понимание алгоритма Schönhage-Strassen (огромное целочисленное умножение)

Мне нужно умножить несколько целых чисел цифр 1000s как можно более эффективно в Python. Числа читаются из файла.Понимание алгоритма Schönhage-Strassen (огромное целочисленное умножение)

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

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

источник

2009-05-14 JPCosta

Один очень важный намек: не пытайтесь реализовать свой собственный БПФ, если вам действительно не нужно. Если он доступен для python, попробуйте использовать FFTW для своих вычислений. Это намного превосходит все, что вы когда-либо могли бы реализовать самостоятельно. Простой БПФ не так уж и трудный, но сложная часть получает его быстро, особенно если числа, которые вы хрустите, не обладают полномочиями двух. – LiKao

@LiKao: Schönhage-Strassen обычно реализуется с использованием вектора фиксированного размера целых чисел произвольного размера и теоретического преобразования чисел, тогда как БПФ, реализованные такими пакетами, как FFTW, используют элементы с плавающей запятой и фиксированным размером - поэтому они не являются на самом деле очень полезно. –

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

источник

2009-05-14 07:35:58 schnaader

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

источник

2009-05-14 07:34:22

+1, хотя я надеюсь, что OP это осознает. Википедия, которую он связал, объясняет это очень рано («начинает превосходить старые методы [...] (от 10 000 до 40 000 десятичных цифр»). – schnaader

извините, я знаю об этом, я хотел спросить «несколько цифр в тысячу долларов», Я отредактирую вопрос. – JPCosta

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

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

источник

2011-11-03 03:35:25

Ну, а как насчет PyopenCL? – user2284570

Понимание алгоритма Schönhage-Strassen (огромное целочисленное умножение)

ответ

Смежные вопросы