Разделив большие числа на более мелкие, исследователи переписали фундаментальное математическое ограничение скорости. Сохранить статью Прочитать позже
Введение
Четыре тысячи лет назад вавилоняне изобрели умножение. В прошлом месяце математики усовершенствовали его.
18 марта два исследователя описали самый быстрый из когда-либо найденных методов умножения двух очень больших чисел. Эта работа стала кульминацией длительного поиска наиболее эффективного способа выполнения одной из самых базовых математических операций.
«Все думают, что метод, которому их учат в школе, — лучший, но на самом деле это активная область исследований», — сказал Йорис ван дер Хувен, математик из Французского национального центра научных исследований и один из соавторов.
Сложность многих вычислительных задач, от вычисления новых знаков числа «пи» до нахождения больших простых чисел, сводится к скорости умножения. Ван дер Хувен описывает их результат как установление своего рода математического предела скорости решения многих других типов задач.
«В физике есть важные константы, такие как скорость света, которые позволяют описывать всевозможные явления», — сказал ван дер Хувен. «Если вы хотите узнать, насколько быстро компьютеры могут решать определённые математические задачи, то целочисленное умножение становится своего рода базовым строительным кирпичиком, относительно которого можно выразить эти скорости».
Почти все учатся умножать одинаково. Мы складываем два числа один на другой, умножаем каждую цифру нижнего числа на каждую цифру верхнего и в конце выполняем сложение. Если вы умножаете два двузначных числа, вам в итоге нужно выполнить четыре умножения меньшего размера, чтобы получить итоговый результат.
Метод начальной школы, или метод переноса, требует около n² шагов, где n — количество цифр каждого умножаемого числа. Таким образом, трёхзначные числа требуют девяти умножений, а стозначные — 10 000.
Метод переноса хорошо работает для чисел, состоящих всего из нескольких разрядов, но он даёт сбои при умножении чисел, состоящих из миллионов или миллиардов разрядов (что компьютеры и делают для точного вычисления числа «пи» или в рамках всемирного поиска больших простых чисел). Чтобы умножить два числа, состоящих из миллиарда разрядов, требуется 1 миллиард в квадрате, или 1018, умножений, что заняло бы у современного компьютера около 30 лет.
На протяжении тысячелетий считалось, что не существует более быстрого способа умножения. В 1960 году 23-летний российский математик Анатолий Карацуба посетил семинар Андрея Колмогорова, одного из величайших математиков XX века. Колмогоров утверждал, что не существует общей процедуры умножения, требующей менее n² действий. Карацуба считал, что такая процедура существует, и после недели поисков он её нашёл.
Метод Карацубы заключается в разбиении числа на разряды и их перекомпоновке новым способом, позволяющим заменить большое количество умножений небольшим количеством сложений и вычитаний. Этот метод экономит время, поскольку сложение занимает всего 2n шагов, а не n2.
«Со сложением вы справляетесь на год раньше в школе, потому что это намного проще, это можно сделать за линейное время, почти так же быстро, как читать числа справа налево», — сказал Мартин Фюрер, математик из Университета штата Пенсильвания, который в 2007 году создал самый быстрый на тот момент алгоритм умножения.
Работая с большими числами, можно повторить процедуру Карацубы, разбив исходное число на почти столько же частей, сколько в нём цифр. При этом с каждым разбиением вы заменяете многошаговые умножения на сложения и вычитания, требующие гораздо меньшего количества шагов.
«Некоторые умножения можно превратить в сложения, и идея заключается в том, что сложения будут выполняться компьютерами быстрее», — сказал Дэвид Харви, математик из Университета Нового Южного Уэльса и соавтор новой статьи.
Метод Карацубы позволял умножать числа, используя всего n1,58 однозначных умножений. Затем, в 1971 году, Арнольд Шёнхаге и Фолькер Штрассен опубликовали метод, позволяющий умножать большие числа за n × log n × log(log n) мультипликативных шагов, где log n — логарифм n. Для двух чисел длиной в миллиард разрядов метод Карацубы потребовал бы около 165 триллионов дополнительных шагов.
Метод Шёнхаге и Штрассена, используемый компьютерами для умножения огромных чисел, имел два важных долгосрочных последствия. Во-первых, он положил начало использованию метода из области обработки сигналов, называемого быстрым преобразованием Фурье. С тех пор этот метод стал основой всех алгоритмов быстрого умножения.
Во-вторых, в той же статье Шёнхаге и Штрассен высказали предположение, что должен существовать ещё более быстрый алгоритм, чем найденный ими — метод, требующий всего лишь n × log n однозначных операций, — и что такой алгоритм будет самым быстрым из возможных. Их предположение основывалось на догадке, что такая фундаментальная операция, как умножение, должна иметь предел, более элегантный, чем n × log n × log(log n).
«Было своего рода общее мнение, что умножение — настолько важная базовая операция, что, даже с эстетической точки зрения, такая важная операция требует чёткой оценки сложности», — сказал Фюрер. «По общему опыту, математика базовых вещей в конечном итоге всегда оказывается элегантной».
Неуклюжий метод Шёнхаге и Штрассена n × log n × log(log n) продержался 36 лет. В 2007 году Фюрер превзошёл его, и поток идей хлынул. За последнее десятилетие математики находили всё более быстрые алгоритмы умножения, каждый из которых постепенно приближался к n × log n, но так и не достиг его. В прошлом месяце Харви и ван дер Хувен достигли этой цели.
Их метод представляет собой усовершенствование более ранней работы. Он разделяет цифры, использует улучшенную версию быстрого преобразования Фурье и использует другие достижения последних сорока лет. «Мы применяем [быстрое преобразование Фурье] гораздо более радикально, применяем его несколько раз вместо одного и заменяем ещё больше умножений сложениями и вычитаниями», — сказал ван дер Хувен.
Алгоритм Харви и ван дер Хувена доказывает, что умножение можно выполнить за n × log n шагов. Однако это не доказывает, что нет более быстрого способа. Установить, что это наилучший из возможных подходов, гораздо сложнее. В конце февраля группа учёных-компьютерщиков из Орхусского университета опубликовала статью, в которой утверждалось, что если другая недоказанная гипотеза также верна, то это действительно самый быстрый способ умножения.
И хотя новый алгоритм теоретически важен, на практике он мало что изменит, поскольку он лишь немного лучше уже используемых алгоритмов. «Лучшее, на что мы можем надеяться, — это стать в три раза быстрее», — сказал ван дер Хувен. «Это не будет чем-то выдающимся».
Кроме того, изменилась конструкция компьютерного оборудования. Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Разрыв в скорости между умножением и сложением за последние 20 лет значительно сократился, настолько, что в некоторых архитектурах микросхем умножение может выполняться даже быстрее сложения. С некоторыми аппаратными средствами «можно было бы даже ускорить сложение, просто поручив компьютеру выполнить задачу на умножение, что просто невероятно», — сказал Харви.
Аппаратное обеспечение меняется со временем, но лучшие в своём классе алгоритмы остаются неизменными. Независимо от того, какими будут компьютеры в будущем, алгоритм Харви и ван дер Хувена по-прежнему будет самым эффективным способом умножения.
Эта статья была перепечатана на Wired.com и на испанском языке на Investigacionyciencia.es .
Источник: www.quantamagazine.org
