Решена полувековая математическая загадка
Кадр: UNSW Science / YouTube
Математики из Австралии и Франции создали высокоэффективный алгоритм, позволяющий быстро умножать числа, слишком большие для обычных способов. Ученые искали этот метод в течение почти 50 лет с тех пор, как в 1971 году был предложен алгоритм Шенхаге-Штрассена. Об этом пишет издание Science Alert.
Новый алгоритм выполняется за время, равное O(n log n), где n является порядком числа. Он может выполнять операцию умножения с числами, состоящими из более чем миллиарда знаков, в течение менее 30 секунд.
Обычные методы выполняют это действие за время, равное n в степени 1,58-2, и у компьютеров вычисление результата с большими множителями может занять месяцы. Это происходит потому, что, например, умножение двух трехзначных чисел требует девяти операций (каждая