Я хочу знать, какой алгоритм является самым быстрым для умножения двух n-значных чисел? Пространственная сложность может быть смягчена здесь!
21
Я хочу знать, какой алгоритм является самым быстрым для умножения двух n-значных чисел? Пространственная сложность может быть смягчена здесь!
Ответы:
На данный момент алгоритм Фюрера Мартина Фюрера имеет временную сложностьжурнал n( n ) 2Θ (лог∗ ( н ) ) которой используются преобразования Фурье по комплексным числам. Его алгоритм фактически основан на алгоритме Шенхаге и Штрассена, который имеет временную сложность Θ (пжурнал( n ) журнал( журнал( н ) ) )
Другими алгоритмами, которые работают быстрее, чем алгоритм умножения в начальной школе, являются умножение Карацубы, которое имеет временную сложностьO ( nжурнал23) ≈ O ( n1,585) и алгоритм Toom 3, который имеет временную сложность из Θ ( н1,465)
Обратите внимание, что это быстрые алгоритмы. Найти быстрый алгоритм для умножения является открытой проблемой в области компьютерных наук.
Ссылки :
источник
Обратите внимание, что алгоритмы FFT, перечисленные в avi, добавляют большую константу, что делает их непрактичными для чисел, меньших, чем тысячи + бит.
В дополнение к этому списку, есть еще несколько интересных алгоритмов и открытых вопросов:
источник