Загрузка...

Решена полувековая математическая загадка

Кадр: UNSW Science / YouTube


Математики из Австралии и Франции создали высокоэффективный алгоритм, позволяющий быстро умножать числа, слишком большие для обычных способов. Ученые искали этот метод в течение почти 50 лет с тех пор, как в 1971 году был предложен алгоритм Шенхаге-Штрассена. Об этом пишет ЛЕНТА со ссылкой на издание Science Alert.

Новый алгоритм выполняется за время, равное O(n log n), где n является порядком числа. Он может выполнять операцию умножения с числами, состоящими из более чем миллиарда знаков, в течение менее 30 секунд.

Обычные методы выполняют это действие за время, равное n в степени 1,58-2, и у компьютеров вычисление результата с большими множителями может занять месяцы. Это происходит потому, что, например, умножение двух трехзначных чисел требует девяти операций (каждая цифра одного числа перемножается с тремя другими), а двух четырехзначных чисел — уже 16 операций.
Высокоэффективный алгоритм полезен для вычисления произведений только очень больших чисел, например, 10 в степени 214857091104455251940635045059417341952. Теоретически он по скорости превосходит оригинальный метод Шенхаге-Штрассена, в основе которого лежит быстрое преобразование Фурье. Однако ученые опасаются, что в доказательстве их метода могли быть допущены ошибки, поэтому необходимы дальнейшие проверки для подтверждения его работоспособности.
Загрузка...
Категории: в мире, образование
Ключевые слова: математика, решение, задача
статья прочитана 371 раз
добавлена 13 апреля, 09:00

Комментарии

Авторские права на всю информацию, размещенную на веб-сайте Obzor.lt принадлежат редакции газеты «Обзор» и ЗАО «Flobis». Использование материалов сайта разрешено только с письменного разрешения ЗАО "Flobis". В противном случае любая перепечатка материалов (даже с установленной ссылкой на оригинал) является нарушением и влечет ответственность, предусмотренную законодательством ЛР о защите авторских прав. Газета «Обзор»: новости Литвы.
Рейтинг@Mail.ru