Колектив математиків з Університету Нового Південного Уельсу в Австралії і Вищої політехнічної школи Франції розв’язали задачу по швидкому множенню занадто великих чисел. Вчені протягом 50 років шукали оптимальний варіант, з тих пір, як в 1971 році був запропонований алгоритм Шенхаге-Штрассена.
Як пише видання sci-news, новий алгоритм здійснює обчислення за час, що дорівнює O (n log n), де n є порядком числа. Він може виконувати операцію множення з числами, що складаються з більш ніж мільярда знаків, протягом менш ніж 30 секунд. Звичайні методи виконують цю дію за час, що дорівнює n в ступені 1,58-2, і у комп’ютерів обчислення результату з великими множителями може зайняти місяці. Це відбувається тому, що, наприклад, множення двох тризначних чисел вимагає дев’яти операцій (кожна цифра одного числа перемножується з трьома іншими), а двох чотиризначних чисел – вже 16 операцій.
Високоефективний алгоритм корисний для обчислення тільки дуже великих чисел, наприклад, 10 в ступені 214857091104455251940635045059417341952. Теоретично він по швидкості перевершує оригінальний метод Шенхаге-Штрассена, в основі якого лежить швидке перетворення Фур’є. Однак вчені побоюються, що в доказі їх методу могли бути допущені помилки, і необхідні подальші перевірки для підтвердження його працездатності.
