WikiSort.ru - Не сортированное

Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — быстрый метод умножения больших целых чисел. Основной идеей алгоритма является быстрое преобразование Фурье. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году^[1]. Метод требует ${\displaystyle O(N\cdot \log N\cdot \log \log N}$ ) битовых операций, где N — количество двоичных цифр в произведении^[2].

Фактически, метод Шёнхаге — Штрассена является методом умножения многочленов от одной переменной. Он превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 (в десятичной системе счисления) мы выполняем следующие операции.

• Представляем ${\displaystyle 157}$ как ${\displaystyle x^{2}+5x+7}$ , а ${\displaystyle 171}$ — как ${\displaystyle x^{2}+7x+1}$ , где ${\displaystyle x=10}$ .
• Перемножаем многочлены ${\displaystyle x^{2}+5x+7}$ и ${\displaystyle x^{2}+7x+1}$ с помощью быстрого преобразования Фурье. Получаем ${\displaystyle x^{4}+12x^{3}+43x^{2}+54x+7}$ .
• Делая переносы через разряды, получаем ${\displaystyle 2x^{4}+6x^{3}+8x^{2}+4x+7}$ , то есть ${\displaystyle 26847}$ .

Также в алгоритме Шёнхаге — Штрассена можно умножать по модулю чисел Ферма ${\displaystyle 2^{2^{n}}+1}$ , если применять двоичную систему счисления.

Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения.^[3] На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка ${\displaystyle 10^{10000}}$ —${\displaystyle 10^{40000}}$ (от 10 000 до 40 000 десятичных знаков)^[4][5][6].

См. также

• Сложность вычисления (битовая)
• Быстрые алгоритмы
• АГС метод Гаусса
• Метод БВЕ
• Алгоритм Фюрера

Примечания