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

[ksbes]

Ну вообще-то есть алгоритм О(1). Правда его бычно для малых чисел используют, но в теории ничто не мешает его использовать и для любого конечного числа чисел. Таблица умножения.

Тут явно не мешает уточнение формулировок. Всё же речь идёт о манипуляциях с цифрами в позиционных системах исчислений.

Для сравнения - умножению и делению чисел записанных римскими цифрами раньше в университетах именитые учёные (буквально - я не помню, вроде Фибоначи тот же) учились в течении лет. А в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация) умножение и деление - это одно действие сложения.

Так что чётче надо задачу формулировать!

[OlegMax]

в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация)

Научная нотация - это совсем другое

Таблица умножения.

Так любую NP-полную задачу можно свести к O(1). Достаточно простого советского справочника с ответами

[ksbes]

Научная нотация - это совсем другое

Ну не совсем-совсем. Потому и в кавычках. Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).

Достаточно простого советского …

Дело не в этом. А в том, что просто “задача перемножения чисел” в математике вообще как таковая не не то что не решается, а не ставится. Просто за ненадобностью (результат просто есть по определению операции - фактически та же таблица). Ставится задача поиска, например, десятичной записи произведения, зная десятичную запись множителей. Но это - значительно более узкая задача.

[OlegMax]

перемножение флоатов быстрее целых

Откуда вы это взяли?

[ImagineTables]

Сдаётся мне, если число растёт, а разрядность (размер машинного слова) — нет (это очень реалистичное допущение), lookup перестаёт быть O(1) (индекс надо делить), а с ним и алгоритм.

[OlegMax]

del

[MaximArbuzov]

Новый алгоритм работает за время O(n × log n).

Был же уже алгоритм FFT с таким же временем работы и похожий на него NTT.
Как будто в статье не хватает каких-то деталей.

[malkovsky]

У них битовая сложность не n log n. Если вы хотите применять классический nlogn FFT Кули-Тьюки для умножения чисел (вычислили на комплексных корнях -> перемножили -> проинтерполировали), то вместе с n будет расти и точность, требуемая от этих преобразований, уже n log n не получается.

Если на основе NTT, то есть видимо Shonhage-Strassen, та же проблема: для числа длины n нужно поле хотя бы из n элементов, мультипликативная группа, при вычислении на которой из цифр длины О(1) получаются уже значения длины О(log n)

[MaximArbuzov]

Спасибо. Мне кажется, что такого объяснения и не хватает для полноты статьи.

[CitizenOfDreams]

А где и для чего практически используются числа с сотнями десятичных знаков?

[petsernik]

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

[malkovsky]

Да, криптография -- основной пользователь арифметики с большими числами, а это https, сертификаты, подписи и прочая аутентификация, криптовалюта, ...

[faina_sn]

очень крутая статья, прям каеф

[dronperminov]

В то же время математики не знают, можно ли некоммутативно перемножить две матрицы 3х3 быстрее, чем за 23 произведения (алгоритм с 23 произведениями известен ещё с 1976). Казалось бы, всего-то 27 значений, не сотни, не тысячи, но ответа нет...