Новости

Математики открыли новый способ умножения больших чисел

Пара математиков из Австралии и Франции разработала новый способ умножения чисел, решив полувековую алгоритмическую головоломку.

Привычный способ умножения относительно небольших чисел заключается в запоминании таблицы умножения. Однако большие числа сложно умножить быстро, даже если использовать привычный способ умножения столбиком. Длинное умножение, по сути, является алгоритмом, но он не особенно эффективен и слишком медленный. Математики производят умножение, где оба числа имеют по 3 цифры (n = 3), при этом количество задействованных операций умножения фактически равно 9, что является  n2. Проблема заключается в том, что по мере того, как числа становятся больше, количество необходимых операций также увеличивается, всегда представляя n в степени 2. Этот алгоритм длинного умножения был фактически самым продвинутым алгоритмом, который существовал до 1960-х годов. Десять лет спустя пара немецких математиков разработала метод умножения Шёнхаге — Штрассена. Метод требует O(N х logN х loglog N) битовых операций, где N — количество двоичных цифр в произведении. Новый алгоритм представляет собой O(N x logN) битовых операций.

По мнению исследователей, умножение двух чисел на миллиардные цифры в процессе длинного умножения потребует месяцы для расчета, даже если это будет делать компьютер. При использовании алгоритма Шёнхаге — Штрассена это займет менее 30 секунд, а с новым теоретическим доказательством это будет самый быстрый алгоритм умножения, который математически возможен. Учёные полагают, что открытие сможет стать основой для дальнейших исследований в области математических алгоритмов.

Читайте также
Чем отличается «сухой» биолог от «мокрого»? Подборка научных мемов
Чем отличается «сухой» биолог от «мокрого»? Подборка научных мемов
Пифагор в ярости, домашнее животное тарантула, отличие «сухого» биолога от «мокрого»
«Миллиард вакцин за год никто не производил»: основные вызовы в борьбе с COVID-19
«Миллиард вакцин за год никто не производил»: основные вызовы в борьбе с COVID-19
«Мы все в автобусе, который завис над пропастью. Все восемь миллиардов внутри».
Марсианская гонка: страны-участницы и что они запускают
Марсианская гонка: страны-участницы и что они запускают
Такой конкуренции на марсианском направлении еще не было