Алгоритм умножения

Умножение больших чисел может быть выполнено традиционным школьным способом «в столбик». Однако вместо использования массива промежуточных результатов гораздо эффективнее добавлять к произведению каждую новую строку немедленно после ее вычисления.
Если множимое состоит из m слов, множитель – из n слов, то произведение занимает не более m + n слов, независимо от того, выполняется знаковое или беззнаковое умножение. Рассмотрим реализацию умножения неотрицательных целых чисел (um-1, …, u0)b и (vn-1, …, v0)b по основанию b. Следующий алгоритм формирует их произведение (wm + n – 1, …, w0)b:

MULTIPLY (w, v, m, n)
for j = 0, …, m – 1 do wj := 0;
j := 0;
while j < n
do if vj > 0
then i := 0; k := 0;
while i < m
do t := ui * vj + wi+j + k:
wi+j := t mod b;
k :=

;
i := i + l;
wj + m := k;
else wj + m := 0;
j := j + l;
return (wm + n - 1, …,w0)

На каждом шаге алгоритма умножения выполняются неравенства
.
Умножение больших чисел выполняется проще для беззнаковых операндов. Знак произведения получается как результат операции «ИСКЛЮЧАЮЩЕЕ-ИЛИ» над разрядами знака множителей.
Умножение целых чисел может быть существенно ускорено. Например, пусть . Тогда (алгоритм Карацубы)
(11)

Алгоритм Карацубы сводит задачу умножения двух чисел к нескольким задачам умножения чисел меньшей разрядности. Разбиение может осуществляться рекурсивно до тех пор, пока разрядность не уменьшится до поддерживаемой аппаратно (т.е. пока n не достигнет размера машинного слова). В этом случае число элементарных умножений для алгоритма Карацубы асимптотически сходится к .
Пример: 13 * 27 = 100 * 1 * 2 + 10 * (3 * 7 + 1 * 2) + 3 * 7 = 100 * 2 + 10 * (36 –
– 21 – 2) + 21 = 200 + 130 + 21 = 351.
Обобщением алгоритма Карацубы является алгоритм Тома–Кука, в котором множители могут разбиваться более чем на две части. Максимальной скоростью на сегодняшний день обладает алгоритм умножения на основе быстрого преобразования Фурье. В этом случае цифры произведения получаются как коэффициенты свертки цифр множителей, посчитанные с учетом переносов значений между коэффициентами.

Автор: Ярмолик, В. Н.