Алгоритм Шьонхаге — Штрассена

Метод множення Шенхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм множення великих цілих чисел, заснований на швидкому перетворенні Фур'є, потребує $O(N\cdot \log N\cdot \log \log N$) бітових операцій, де $N$ — кількість двійкових цифр у добутку.

Історія

Метод швидкого перетворення Фур'є зі складністю $O(N\cdot \log N)$ став широко відомим 1965 року після публікації статті Джеймса Кулі та Джона Тьюкі.

Застосувати швидке перетворення Фур'є для множення великих чисел запропонував 1968 року Фолькер Штрассен. Разом із Арнольдом Шьоханге вони уточнили метод та опублікували алгоритм 1971 року.

Ідея алгоритму

Фактично — це метод множення многочленів від однієї змінної; перетворюється на алгоритм множення чисел, якщо числа подати як многочлени від основи системи числення, а після отримання добутку многочленів зробити знесення старших розрядів у коефіцієнтах. Наприклад, для множення 157 на 171 (у десятковій системі числення) виконуються такі операції:

• $157$ подається як $x^{2}+5x+7$, а $171$ — як $x^{2}+7x+1$, де $x=10$;
• за допомогою швидкого перетворення Фур'є перемножуються многочлени $x^{2}+5x+7$ і $x^{2}+7x+1$ (результат: $x^{4}+12x^{3}+43x^{2}+54x+7$);
• застосовується знесення старших розрядів у коефіцієнтах многочлена-добутку: $2x^{4}+6x^{3}+8x^{2}+4x+7$.
  Результат: $26847$.

Алгоритм

Основний етапом алгоритму є множення чисел a і b по модулю 2^N+1:

c = a * b (mod 2^N+1)

Підготовчий етап (встановлення параметрів)

Оскільки потрібен повний результат множення (а не залишок по модулю), то на N накладають обмеження:

a*b < 2^N+1, тобто, N >= bits(a) + bits(b)

Вхідні числа поділяють на 2^k частин розміром M біт кожна (M = N/2^k). Це накладає додаткове обмеження на N — воно має націло ділитися на 2^k: N=2^kM. Після цього обидва числа розглядають як поліноми від однієї змінної — основи системи числення (2^M).

Для проміжних розрахунків (після перетворення Фур'є) обрати модуль N' з умови N'=2^kM', де M' >= 2M + k. Такий вибір N' дозволяє уникнути цілочисельного переповнення.

Основний етап (обчислення добутку поліномів методом згортки)

1. Обчислити значення поліномів-множників (A_i, B_i) у точках gⁱ, де:
   • g = 2^{(2N' / 2k)}
   • i = 0 .. 2^k-1.

   такий вибір точок спрощує подальшу інтерполяцію (на кроці 5)

2. Для обох наборів обчислених значень (A_i, B_i) виконати дискретне перетворення Фур'є в кільці $\mathbb {Z} /(2^{N'}+1)\mathbb {Z}$:
   • ${\widehat {A}}_{i}=DFT(A_{i})$
   • ${\widehat {B}}_{i}=DFT(B_{i})$

   оскільки в обох наборах по 2^k значень, застосовується швидке перетворення Фур'є

3. Обчислити образ добутку шляхом попарного множення: ${\widehat {C}}_{i}={\widehat {A}}_{i}*{\widehat {B}}_{i}$

   попарне множення виконується по модулю 2^N';

   воно потребує D=2^k множень (замість D² у звичайному алгоритмі множення поліномів)

4. До образу ${\widehat {C}}$ застосувати обернене перетворення Фур'є: $C_{i}=iDFT({\widehat {C}}_{i})$
5. Побудувати поліном-добуток за його значеннями в 2^k точках ($C_{i}$) шляхом інтерполяції.

Завершальний етап (нормалізація результату)

У коефіцієнтах многочлена-добутку зробити знесення старших розрядів, щоб отримати нормалізований запис числа-добутку в обраній системі числення.

Оскільки у швидкому перетворенні Фур'є (як у прямому, так і в оберненому) застосовуються тільки операції додавання, віднімання та зсуву (яким замінено множення на степені двійки), то власне множення в алгоритмі виконується лише на кроці 3.

Зокрема, алгоритм дозволяє ефективно множити за модулем чисел Ферма $2^{2^{n}}+1$.

Оцінка складності

Як довели у своїй публікації Шенхаге і Штрассен, алгоритм потребує $O(N\cdot \log N\cdot \log \log N$) бітових операцій, де $N$ — кількість двійкових цифр у добутку.

Порівняння з іншими методами

На практиці метод Шенхаге — Штрассена починає перевершувати раніше відомі класичні методи, такі як множення Карацуби та алгоритм Тоома — Кука (узагальнення методу Карацуби), починаючи з цілих чисел порядку $10^{10000}$—$10^{40000}$ (від 10 000 до 40 000 десяткових знаків).

Метод вважався асимптотично найшвидшим до винайдення алгоритму Фюрера (2007 рік), який має меншу асимптотичну оцінку: $O(n\log n\cdot 2^{O(\log ^{*}n)})$, де log^*n — повторний логарифм. Утім, перевага алгоритму Фюрера стає помітною лише для настільки великих чисел, які практично не трапляються.