Забудьте свои таблицы умножения: вот новый, гораздо более эффективный метод

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

Давайте сначала начнем с плохих новостей: это математическое открытие не позволит вам ускорить ваши банковские счета или вычислить в мгновение ока количество яиц, которые нужно купить, чтобы приготовить блины на масленицу. Алгоритм, разработанный Дэвидом Харви из Университета Нового Южного Уэльса в Австралии и Йорисом ван дер Хувеном из Политехнической школы, на данный момент применим только к очень большим числам, с другой стороны, если он недоступен для людей, он может оказаться очень полезным для оптимизации вычислительной скорости компьютеров и для программирования.

Вспомним сначала, как выполнить умножение между двумя числами: надо наложить оба числа и вычислить для каждой цифры произведение умножения с цифрами числа ниже. Для 3-значного целого числа это дает нам в общей сложности 3 x 3 операции для выполнения. Вообще говоря, для целого числа n необходимо выполнить n ² операции (которые также можно отметить n ^2) .

Гипотеза 1971 года, которую еще предстоит продемонстрировать

В 1962 году математик Анатолий Карацуба уже успел снизить этот порог до n ^1,58, а в 1971 году Арнольд Шенхаге и Фолькер Штрассен разработали алгоритм, еще больше уменьшающий решение до n (log( n )) log(N), где log-функция логарифма.

"С помощью этой формулы умножение двух многомиллиардных чисел занимает всего 26 секунд, по сравнению с 6 месяцами с традиционным методом", - уверяет Дэвид Харви в журнале New Scientist.

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

Лучше оценить время вычислений компьютеров

Это только что доказали Харви и Ван дер Ховен в своей демонстрации, опубликованной 18 марта прошлого года. Таким образом, для n = 2 для нормального умножения требуется 4 операции, против примерно 2,41 с их методом. При n = 1.000 количество операций уменьшается с 10.000 до 200 ! Но есть одна загвоздка: этот новый алгоритм на данный момент действителен только для чисел размером больше 2^(1.729^12), то есть целые числа в несколько миллиардов миллиардов миллиардов цифр.

"Наша демонстрация предназначена для чисто теоретических целей", - признают два автора, которые не рассматривали способ применения своей формулы к меньшим числам. Тем не менее этот метод может, например, позволить разработчикам оценить вычислительное время, необходимое для выполнения их собственных алгоритмов. В любом случае это может быть конец истории : "я буду очень удивлен , если мы найдем новый алгоритм, способный бить n(log(n)), - говорит Дэвид Харви.

Что в итоге?

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