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

Метод умножения Шёнхаге — Штрассена  — быстрыйметод умножения больших целых чисел. Основной идеей алгоритма являетсябыстрое преобразование Фурье. Он был построен Арнольдом Шёнхагеи Фолькером Штрассеном в 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десятичных знаков).