Еще один способ быстро умножать простые числа
Дэвид Харли, доцент из Университета Нового Южного Уэльса в Сиднее обратился к алгоритму Шёнхаге — Штрассена, разработанному двумя немецкими математиками. В период с 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 лет охотилось за таким удобным способом работы с огромными простыми числами — и теперь он наконец в нашем распоряжении», — говорит сам Харви.
