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

Question

Я знаю, что компьютеры используют метод shift и add для умножения двух чисел.

Бит мудрый сдвиг умножается и делит на полномочия двух. Эта операция выполняется быстрее, чем команда умножения. Умножение на константу и деление на константу может быть реализовано с использованием последовательности сдвигов и добавлений или вычитаний.

((x << 2) + x) << 1 // Here 10*x is computed as (x*2^2 + x)*2 
(x << 3) + (x << 1) // Here 10*x is computed as x*2^3 + x*2 

Но есть ли более быстрый алгоритм для этого?

Thx за помощь :)

Answer 1

Составители использовать любое сочетание нативных инструкции по сборке является наиболее эффективным.

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

Вы не будете бить компилятор в этой игре.

Answer 2

Для очень больших n с (> 1000 цифр примерно), существуют специализированные алгоритмы, в порядке возрастания прочности они: Karatsuba, Toom-Cook и, наконец, монстр 100000 значных умножений: Schönhage-Strassen.

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