Интернет магазин китайских планшетных компьютеров

Компьютеры - Метод умножения Шёнхаге Штрассена

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

Фактически, метод Шёнхаге — Штрассена является методом умножения многочленов от одной переменной. Он превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 мы выполняем следующие операции.

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

Также в алгоритме Шёнхаге — Штрассена можно умножать по модулю чисел Ферма , если применять двоичную систему счисления.

Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения. На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука, начиная с целых чисел порядка 10—10.