Какой самый быстрый алгоритм для умножения двух n-значных чисел?

21

Я хочу знать, какой алгоритм является самым быстрым для умножения двух n-значных чисел? Пространственная сложность может быть смягчена здесь!

Энди
источник
1
Вас интересует теоретический вопрос или практический вопрос?
Юваль Фильмус
Оба, но более склонны к практическому!
Энди
1
Для практического вопроса я рекомендую использовать GMP. Если вам интересно, что они используют, посмотрите документацию или исходный код.
Юваль Фильмус
Никто не знает. Мы еще не нашли это.
Джефф

Ответы:

22

На данный момент алгоритм Фюрера Мартина Фюрера имеет временную сложность Nжурнал(N)2Θ(Lограмм*(N)) которой используются преобразования Фурье по комплексным числам. Его алгоритм фактически основан на алгоритме Шенхаге и Штрассена, который имеет временную сложность Θ(Nжурнал(N)журнал(журнал(N)))

Другими алгоритмами, которые работают быстрее, чем алгоритм умножения в начальной школе, являются умножение Карацубы, которое имеет временную сложность О(Nжурнал23)О(N1,585) и алгоритм Toom 3, который имеет временную сложность из Θ(N1,465)

Обратите внимание, что это быстрые алгоритмы. Найти быстрый алгоритм для умножения является открытой проблемой в области компьютерных наук.

Ссылки :

  1. Алгоритм Фюрера
  2. БПФ умножение больших чисел
  3. Быстрое преобразование Фурье
  4. Умножение Кука-Кука
  5. Алгоритм Шёнхаге – Штрассена
  6. Алгоритм Карацубы
AVI
источник
Обратите внимание на недавнюю работу D. Harvey и J. van der Hoeven (март 2019), описывающую алгоритм со сложностью . О(NперN)
hardthth
9

Обратите внимание, что алгоритмы FFT, перечисленные в avi, добавляют большую константу, что делает их непрактичными для чисел, меньших, чем тысячи + бит.

В дополнение к этому списку, есть еще несколько интересных алгоритмов и открытых вопросов:

  • Умножение линейного времени на модели ОЗУ (с предварительным вычислением)
  • Умножение на константу является сублинейным ( PDF ) - это означает сублинейное количество сложений, которое в сумме даетразрядность. Это по сути эквивалентно длинному умножению (где вы сдвигаете / прибавляете на основе числас в нижнем числе), которое является, но сускорение.1O(n2)O(logn)О(N2журналN)1О(N2)О(журналN)
  • Система счисления остатков и другие представления чисел; умножение почти линейного времени. Недостатком является то, что умножение является модульным, и {обнаружение переполнения, четность, сравнение по величине} являются такими же сложными или почти такими же сложными, как преобразование числа обратно в двоичное или подобное представление и выполнение традиционного сравнения; это преобразование, по крайней мере, так же плохо, как и традиционное умножение (на данный момент AFAIK).
    • Другие представления:
      • [ Логарифмическое представление ]: умножение - это дополнение логарифмического представления. Пример:
        16×32знак равно2журнал216+журнал232знак равно24+5знак равно29
        • Недостатком является то, что преобразование в логарифмическое представление и из него может быть таким же сложным, как умножение или сложнее, представление также может быть дробным / иррациональным / приблизительным и т. Д. Другие операции (сложение?), Вероятно, более сложны.
      • Каноническое представление : представьте числа как показатели простой факторизации. Умножение - это сложение показателей. Пример:
        36×48знак равно3251×223141знак равно22324151
      • Недостатком является то, что требуются факторы или факторизация, гораздо более сложная проблема, чем умножение Другие операции, такие как сложение, вероятно, очень сложны.
Реал Слав
источник
1
Я полагаю, что подход, основанный на теореме остатка / китайского остатка, с правильными модулями может привести к ускорению по сравнению с традиционным умножением даже с обратным преобразованием; в какой-то момент это было в главе 4 TAOCP, по крайней мере, в качестве сноски. (Это все еще не близко к методам, основанным на FFT, но это интересная историческая заметка)
Стивен Стадницки
@ StevenStadnicki о, круто, мне нужно посмотреть на это тогда; ты случайно не знаешь сложности?
Реал Слав