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

Не плутати з алгоритмом Штрассена для множення матриць.

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

Історія

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

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

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

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

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

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

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

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

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

Примітки

1. Bürgisser P., Clausen M., Shokrollahi A. Algebraic Complexity Theory. — Berlin : , 1997. — 618 p. — ..
2. Knuth, 2008, Section 4.3.3 С.
3. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — С. 281—292.
4. Meter van R., Itoh K. M. Fast quantum modular exponentiation // Physical Review A. — 2005. — Т. 71. з джерела 7 лютого 2006. Процитовано 2023-05-28.
5. Coronado García L. C. Can Schönhage multiplication speed up the RSA encryption or decryption? // University of Technology. — Darmstadt, 2005. з джерела 29 грудня 2009. Процитовано 2023-05-28.
6. Fürer M. Faster integer multiplication // STOC 2007 Proceedings. — 2007. — С. 57—66. з джерела 25 квітня 2013.