1-й алгоритм умножения (оптимизация следствия)

Он связан с именем советского и российского математика Анатолия Алексеевича Карацуба. В 1960 году ему пришла в голову мысль, что можно оптимизировать имеющийся алгоритм умножения чисел. Он нашел способ перемножения чисел за 2n шагов вместо n², предложив вместо большого количества умножений провести меньшее количество сложений и вычитаний. Метод Карацубы сделал возможным умножать числа с использованием лишь n^1,58 умножений на однозначное число. Для умножения двух чисел из миллиарда знаков каждое метод Карацубы потребует 165 трлн шагов. Его преимущество проявляется, начиная с чисел, имеющих не менее 10 000 десятичных разрядов.

2-й алгоритм умножения (оптимизация процесса)

1971 г. Два немецких математика Арнольд Шёнхаге и Фолькер Штрассен опубликовали метод, позволяющий умножать большие числа за n × log n × log(log n) небольших умножений. Они же предположили существование более эффективного алгоритма, требующего всего n × log n умножений на один знак. В 2007 г. швейцарский математик Мартин Фюрер из университета штата Пенсильвания в США предложил асимптотически более быстрый метод с числом шагов на знак n × log n × 2^log*n, где log*n – итерированный алгоритм n. 

3-й алгоритм умножения (изменение причины, выход на новый уровень)

За последнее десятилетие математики находили всё более быстрые алгоритмы умножения, каждый из которых постепенно подползал к отметке в n × log n, не совсем достигая её. В марте 2019 г. появляется алгоритм Харви и ван дер Хувена. Он доказывает, что умножение можно провести за n × log n шагов на один знак.

“Я был очень удивлен, что это было сделано”, – говорит ученый-теоретик Мартин Фюрер of Penn State. из Пенсильванского университета. Он обнаружил еще одно ускорение умножения в 2007 году, но отказался от дальнейшего совершенствования. – “Мне это казалось совершенно безнадежным.” (из ScienceNews)

Из публикаций в СМИ: Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге-Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее.

Но для текущих задач: «Всё, на что мы можем надеяться, это на трёхкратное ускорение, — сказал ван дер Хувен. – Ничего запредельного».

«В физике есть важные константы типа скорости света, позволяющие вам описывать всякие явления, — сказал ван дер Хувен. – Если вы хотите знать, насколько быстро компьютеры могут решать определённые математические задачи, тогда перемножение целых чисел возникает в виде некоего базового строительного блока, по отношению к которому можно выразить такую скорость».