Метод умножения Шёнхаге Штрассена

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

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

 Также в алгоритме Шёнхаге — Штрассена можно умножать по модулю чисел Ферма 22n+1, если применять двоичную систему счисления.
 Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения. На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка 10100001040000 (от 10 000 до 40 000 десятичных знаков).