Метод умножения Шёнхаге — Штрассена () — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует ) битовых операций, где — количество двоичных цифр в произведении..
Изобретён Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году.
Фактически является методом умножения многочленов от одной переменной, превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 (в десятичной системе счисления) выполняются следующие операции: представляется как , а — как , где ; перемножаются многочлены и с помощью быстрого преобразования Фурье, результат — ; применяются переносы через разряды: , то есть .
Также в алгоритме можно умножать по модулю чисел Ферма , если применять двоичную систему счисления.
Метод считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был изобретён алгоритм Фюрера с лучшей оценкой сложности. На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка — (от 10 000 до 40 000 десятичных знаков)Overview of Magma V2.9 Features, arithmetic section : Discusses practical crossover points between various algorithms..
Примечания
Категория:Длинная арифметика