Быстрое умножение чисел большой разрядности

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

Рассмотрим случай целых чисел и выберем вначале тогда сомножители А и В можно представить в виде где

Произведение чисел А и В определится как

Для того чтобы вычислить это произведение, надо произвести четыре умножения -разрядных чисел, две операции сдвига и три операции сложения, следовательно,

В тоже время совершенно очевиден и другой алгоритм вычисления произведения

Время вычисления произведения по этому алгоритму

Обычно том и второй алгоритм оказывается более быстрым.

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

меньшей величине. Какова эта величина для произвольного Оказывается, что 1163

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

Для -разрядных чисел, представленных в двоичной системе счисления, существуют алгоритмы [16], которые позволяют вычислить -разрядное произведение за время меньшее, чем шагов. Если при умножении двоичных чисел использовать быстрое преобразование Фурье, то

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