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

Метод множення Шенхаге — Штрассена (англ. 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$.

Також алгоритм дозволяє множити за модулем чисел Ферма $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 — повторний логарифм. Утім, різниця в часі виконання між цими двома методами стає помітною лише для настільки великих чисел, які практично не трапляються.