Дэвид Харли, доцент из Университета Нового Южного Уэльса в Сиднее обратился к алгоритму Шенхаге – Штрассена, разработанному двумя немецкими математиками. В период с 1971 года по 2007 это был самый быстрый способ умножения чисел, пока ему на смену не пришла альтернатива (справедливости ради стоит отметить, что используют ее крайне редко).
Лайфхак для истинных гуманитариев: хитрый способ быстро умножать простые числа
Умножение длинных чисел в уме — настоящая головная боль для всех детей с самой начальной школы. Однако математик разработал новый метод умножения больших чисел, который намного эффективнее привычного нам.
Кадр из видео
Шенхаге и Штрассен предсказали существование алгоритма умножения n-значных чисел с использованием базовых операций формата n * log (n). С тех пор прошло несколько десятилетий, но лишь теперь появилось первое доказательство этой гипотезы.
Так в чем же суть? Для примера Харви выбрал умножение чисел 314 и 159 — с подобными числами мы сталкиваемся каждый день. Обычно, чтобы решить подобное уравнение, большинство людей перемножает каждый отдельный номер, а затем складывают суммы. Так, 9 умножается на 4,1 и 3, затем 5 умножается на 4, 1 и 3, и так далее. В результате сложения всех результатов и получается искомое 9-значное число.
Этот метод называется n2, потому что число n умножается на n несколько раз. Получите ли вы правильный ответ? Безусловно. Однако еще в 1971 году немцы придумали, как ускорить процесс. Они записывали его как n * log (n). Напомним, что log — это сокращение от «логарифма», который помогает нам расшифровывать числа, возведенные в степень. Например, 2⁵ = 32, но если записать это уравнение логарифмически, то получится log₂ (32) = 5. Звучит просто, однако по-настоящему логарифмы начинают упрощать процесс в работе с крупными числами.
Харви уверен, что метод Шенхаге-Штрассена очень практичен. По его словам, если обычному компьютеру дать задачу перемножить между собой два числа с миллиардом знаков в каждом, используя «школьный» метод — это заняло бы месяцы. А если дать ему ту же задачу, но использовать при этом подход с логарифмами, то вся операция займет... от силы секунд 30.
Впрочем, и тут есть пределы. математик отмечает, что если число знаков будет составлять триллион и больше, то здесь пригодится алгоритм, разработанный Харви и его сотрудником Йорисом ван дер Хувеном в Политехнической школе во Франции в 2007 году. «С его помощью можно будет вычислить значение числа "пи" с еще большей точностью. Человечество 50 лет охотилось за таким удобным способом работы с огромными простыми числами — и теперь он наконец в нашем распоряжении», — говорит сам Харви.