Вычисление результата с большими множителями может занять месяцы, а найденный алгоритм позволяет найти решение за полминуты.
Коллектив математиков из Университета Нового Южного Уэльса в Австралии и Высшей политехнической школы Франции решили задачу по быстрому умножению слишком больших чисел. Ученые в течение 50 лет искали оптимальный вариант, с тех пор, как в 1971 году был предложен алгоритм Шенхаге-Штрассена, пишет издание sci-news.
Новый алгоритм производит вычисления за время, равное O (n log n), где n является порядком числа. Он может выполнять операцию умножения с числами, состоящими из более чем миллиарда знаков, в течение менее чем 30 секунд.
Обычные методы выполняют это действие за время, равное n в степени 1,58-2, и у компьютеров вычисление результата с большими множителями может занять месяцы. Это происходит потому, что, например, умножение двух трехзначных чисел требует девяти операций (каждая цифра одного числа перемножается с тремя другими), а двух четырехзначных чисел — уже 16 операций.
Высокоэффективный алгоритм полезен для вычисления произведений только очень больших чисел, например, 10 в степени 214857091104455251940635045059417341952. Теоретически он по скорости превосходит оригинальный метод Шенхаге-Штрассена, в основе которого лежит быстрое преобразование Фурье. Однако ученые опасаются, что в доказательстве их метода могли быть допущены ошибки, и необходимы дальнейшие проверки для подтверждения его работоспособности.
Ранее Lenta.UA сообщала о новой космологической теории происхождения вселенной.
Фото: rambler, MIT OpenCourseWare
Новости
Различие между когтями собак и кошек объяснили биологи
00:00 19 май 2024.
В Минобороны отчитались о числе граждан, обновивших данные через «Резерв+»
23:00 18 май 2024.
Очередной российский штурмовик сбили украинские зенитчики
22:00 18 май 2024.
Какие области завтра будут без света, сообщили в «Укрэнерго»
21:00 18 май 2024.
ВСУ вышли из еще одного села возле Волчанска
20:00 18 май 2024.
Опасные для людей последствия солнечных бурь назвали ученые
19:30 18 май 2024.
Последние дни Помпеи Parimatch, или Криминальная эпопея Мельничука – Клищара: треть холдинга хотят заполучить люди с уголовным прошлым
18:55 18 май 2024.
Избрана мера пресечения для стрелявшего в словацкого премьера Фицо
17:45 18 май 2024.
Украинские дальнобойщики перекрыли трассу Киев – Одесса в двух областях
17:10 18 май 2024.