Математики научились за полминуты перемножать числа из миллиарда знаков

Как сообщило издание Science Alert, математики по всему миру бились над созданием такого алгоритма последние 50 лет. В 1971 году был предложен алгоритм Шенхаге-Штрассена, но он слишком медленный для такой сложной задачи.

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

Сами ученые заявили, что их метод может превосходить алгоритм Шенхаге-Штрассена, однако не исключили, что допустили ошибку. Новый метод еще предстоит много раз перепроверить.

Математики заявили, что не могут поверить в работоспособность алгоритма этих двух исследователей, но, подтвержденный, он станет «главным достижением в вычислительной истории».