Хабрахабр

[Перевод] Математики обнаружили идеальный способ перемножения чисел

Разбивая крупные числа на мелкие, исследователи превысили фундаментальное математическое ограничение скорости

Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.

Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики. 18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел.

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

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

Записываем числа в столбик, перемножаем верхнее число на каждую цифру нижнего (с учётом разрядов) и складываем результат. Почти все учатся перемножать числа одинаково. При перемножении двух двузначных чисел приходится проделать четыре более мелких перемножения для получения итогового результата.

Вычисления с трёхзначными числами требуют девяти перемножений, а со стозначными – 10 000. Школьный метод "переноса" требует выполнения n2 шагов, где n – количество цифр в каждом из перемножаемых чисел.

Чтобы перемножить два числа с миллиардом цифр нужно будет произвести миллиард в квадрате, или 1018, умножений – на это у современного компьютера уйдёт порядка 30 лет. Метод переноса нормально работает с числами, состоящими из нескольких цифр, однако начинает буксовать при перемножении чисел, состоящих из миллионов или миллиардов цифр (чем и занимаются компьютеры при точном подсчёте π или при всемирном поиске больших простых чисел).

Затем в 1960 году 23-летний советский и российский математик Анатолий Алексеевич Карацуба посетил семинар, который вёл Андрей Николаевич Колмогоров, советский математик, один из крупнейших математиков XX века. Несколько тысячелетий считалось, что быстрее перемножать числа нельзя. Карацуба решил, что такой способ есть – и после недели поисков он его обнаружил. Колмогоров заявил, что не существует обобщённого способа умножения, требующего меньше, чем n2 операций.


Анатолий Алексеевич Карацуба

Метод экономит время, поскольку на сложения уходит всего 2n шагов вместо n2. Умножение Карацубы заключается в разбиении цифр числа и повторной их комбинации новым способом, который позволяет вместо большого количества умножений провести меньшее количество сложений и делений.


Традиционный метод умножения 26х63 требует четыре умножения на однозначное число и несколько сложений


Умножение Карацубы 26х63 требует трёх умножений на однозначное число и несколько сложений и вычитаний.
a) разбиваем числа
b) перемножаем десятки
c) перемножаем единицы
d) складываем цифры
e) перемножаем эти суммы
f) считаем e – b – c
g) собираем итоговую сумму из b, c и f

При росте количества знаков в числах метод Карацубы можно использовать рекурсивно.


Традиционный метод умножения 2531х1467 требует 16 умножений на однозначное число.


Умножение Карацубы 2531х1467 требует 9 умножений.

«Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо», — сказал Мартин Фюрер, математик из Пенсильванского государственного университета, создавший в 2007 быстрейший на то время алгоритм умножения.

И с каждым разбиением вы меняете умножение, требующее выполнения многих шагов, на сложение и вычитание, требующие куда как меньше шагов. Имея дело с крупными числами, умножение Карацубы можно повторять рекурсивно, разбивая изначальные числа почти на столько частей, сколько в них знаков.

«Несколько умножений можно превратить в сложения, учитывая, что с этим компьютеры будут справляться быстрее», — сказал Дэвид Харви, математик из Университета Нового Южного Уэльса и соавтор новой работы.

Затем в 1971 году Арнольд Шёнхаге и Фолькер Штрассен опубликовали метод, позволяющий умножать большие числа за n × log n × log(log n) небольших умножений. Метод Карацубы сделал возможным умножать числа с использованием лишь n1,58 умножений на однозначное число. Для умножения двух чисел из миллиарда знаков каждое метод Карацубы потребует 165 трлн шагов.


Йорис ван дер Хувен, математик из Французского национального центра научных исследований

Во-первых, он ввёл в использование технику из области обработки сигналов под названием быстрое преобразование Фурье. Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел, и привёл к двум другим важным последствиям. С тех пор эта техника была основой всех быстрых алгоритмов умножения.

Это предположение было основано на ощущении, что у такой фундаментальной операции, как умножение, ограничение операций должно записываться как-то более элегантно, чем n × log n × log(log n). Во-вторых, в той же работе Шёнхаге и Штрассен предположили возможность существования ещё более быстрого алгоритма – метода, требующего всего n × log n умножений на один знак – и что такой алгоритм будет наибыстрейшим из возможных.

– По опыту мы знаем, что математика базовых вещей в итоге всегда оказывается элегантной». «Большинство в общем-то сошлось на том, что умножение – это такая важная базовая операция, что с чисто эстетической точки зрения ей требуется красивое ограничение по сложности, — сказал Фюрер.

В 2007 году Фюрер побил этот рекорд, и всё завертелось. Нескладное ограничение Шёнхаге и Штрассена, n × log n × log(log n), держалось 36 лет. Затем в марте этого года Харви и ван дер Хувен достигли её. За последнее десятилетие математики находили всё более быстрые алгоритмы умножения, каждый из которых постепенно подползал к отметке в n × log n, не совсем достигая её.

Он разбивает числа на знаки, использует улучшенную версию быстрого преобразования Фурье, и также пользуется другими прорывами, сделанными за последние 40 лет. Их метод является улучшением большой работы, проделанной до них. «Мы используем быстрое преобразование Фурье гораздо более грубо, используем его несколько раз, а не один, и заменяем ещё больше умножений сложением и вычитанием», — сказал ван дер Хувен.

Однако он не доказывает отсутствия более быстрого метода. Алгоритм Харви и ван дер Хувена доказывает, что умножение можно провести за n × log n шагов. В конце февраля команда специалистов по информатике из Орхусского университета опубликовала работу, где утверждает, что если одна из недоказанных теорем окажется верной, то этот метод и вправду будет скорейшим из способов умножения. Гораздо сложнее будет установить, что их подход максимально быстрый.

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

Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Кроме того, поменялись схемы компьютерного оборудования. Используя определённые виды оборудования, «можно ускорить сложение, заставляя компьютер умножать числа, и это какое-то безумие», — сказал Харви. Разрыв в скоростях умножения и сложения с тех пор серьёзно уменьшился, в результате чего на некоторых чипах умножение может даже обгонять сложение.

Вне зависимости от того, как компьютеры будут выглядеть в будущем, алгоритм Харви и ван дер Хувена всё ещё будет самым эффективным способом умножать числа. Оборудование меняется со временем, но лучшие алгоритмы своего класса вечны.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть