Вирішена піввікова математична загадка

Опубликованно 04.08.2019 00:06

Математики з Австралії і Франції створили високоефективний алгоритм, що дозволяє швидко множити числа, занадто великі для звичайних способів. Вчені шукали цей метод протягом майже 50 років з тих пір, як в 1971 році був запропонований алгоритм Шенхаге-Штрассена. Про це пише видання Science Alert.

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

Звичайні методи виконують це дія за час, рівний n ступеня 1,58-2, і у комп'ютерів обчислення результату з великими множниками може зайняти місяці. Це відбувається тому, що, наприклад, множення двох тризначних чисел вимагає дев'яти операцій (кожна цифра одного числа перемножується з трьома іншими), а двох чотиризначних чисел — вже 16 операцій.

Високоефективний алгоритм корисний для обчислення творів тільки дуже великих чисел, наприклад, 10 в ступені 214857091104455251940635045059417341952. Теоретично він перевершує по швидкості оригінальний метод Шенхаге-Штрассена, в основі якого лежить швидке перетворення Фур'є. Проте вчені побоюються, що в доказі їх методу могли бути допущені помилки, тому необхідні подальші перевірки для підтвердження його працездатності.Що відбувається в Росії і в світі? Пояснюємо на нашому YouTube-каналі. Підпишись!window._settings.components.eagleplayer = window._settings.components.eagleplayer || {}; window._settings.components.eagleplayer.enabled = true; window._settings.components.eagleplayer.templates = {"multiplayer":["9116","10737","10738","10739","10740"],"scroll":["10409","10410","10737","10738","10814"]}; window._settings.components.eagleplayer.relatedVideosHeight = 185;

Категория: Разное