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

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

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

Чтобы понять суть этого «узкого места», обратите внимание на то, как «школьный» алгоритм справляется с увеличением размера чисел. При умножении двух двузначных чисел выполняется четыре однозначных умножения. Если перейти к паре трёхзначных чисел, то потребуется девять однозначных умножений. Нагрузка растёт пропорционально квадрату количества разрядов (n², где n — количество разрядов в умножаемых числах). При анализе подобного алгоритма компьютерные учёные не измеряют скорость в секундах, поскольку она зависит от аппаратного обеспечения. Вместо этого они подсчитывают количество вычислительных шагов. Они также игнорируют второстепенные детали, такие как время, необходимое для переноса единицы при умножении. Когда числа становятся достаточно большими, эти низкоуровневые операции перестают иметь значение, поскольку их полностью затмевают более ресурсоёмкие операции. Информатики обозначают количество шагов с помощью так называемой нотации «большого O»: например, алгоритм, который учат в начальной школе, требует O(n²) шагов, что читается как «порядка n в квадрате». В общих чертах, если числа в два раза длиннее, для выполнения алгоритма требуется в четыре раза больше вычислительной работы. Если числа в тысячу раз длиннее, требуется в миллион (1 000 в квадрате) раз больше работы.

>>

Источник: habr.com