2.4. Быстрое умножение

2.4.1. Быстрое умножение чисел

При обычном умножении столбиком нам потребуется n² операций, где n – количество разрядов чисел. Попробуем произвести умножение чисел быстрее. Для этого поступим следующим образом:

Пусть x и y – два n-разрядных числа (n = 2k).

Разобьем их запись пополам, т.е. на два отрезка длины k;

x = a · 2^k + b

, где

y = c · 2^k + d

x = x₁x₂…x_k x_k+1…x_2k

a = старшие b = младшие

разряды разряды

y = y₁y₂…y_k y_k+1…y_2k

c = старшие d = младшие

разряды разряды

Рассмотрим умножение x · y по обычным формулам:

4 произведения

x·y = (a·2^k+b)(c·2^k+d) = a×c·2^k+(a×d + b×c)·2^k + b×d (2.7)

1 Суммирование

При перемножении по (2.7) получаем рекуррентную формулу, для вычисления трудоёмкости:

T(n) = 4·T(n/2) + 1·n

4 Произведения чисел вдвое меньшей

одно сложение

Таким образом, в (2.7) четыре произведения и одно сложение. Попробуем обойтись меньшим количеством произведений для умножения двух числе по формуле (2.7). Рассмотрим модификацию формулы (2.7) – формулу (2.8).

Тогда xy = v 2^2k+(u – v – w)2^k + w (2.8)

При перемножении чисел по (2.8) нам потребуется 3 умножения и 4 действия сложения и вычитания. Итого получаем трудоемкость:

T(n) = 3 T(n/2) + 4n. (2.9)

Временно забудем, что числа (a+b) и (c+d) могут быть не k-разрядные, а k+1-разрядные. Организуем процесс умножения двух n-разрядных чисел по формуле (2.8) следующим образом: на входе имеем два длинных числа. Каждое из них разобьем пополам, и получается, что нам нужно 3 раза перемножить числа вдвое меньшей разрядности. Каждое из этих чисел снова делим пополам и перемножаем по формуле (2.8). Подобная процедура дробления осуществляется до тех пор, пока в результате очередного разделения не получатся одноразрядные числа, которые перемножаем по обычной таблице умножения.

Оценим трудоемкость подобных вычислений по формуле (2.8). Она оценивается по рекуррентной формуле (2.9).

Теорема 2.2. Если трудоемкость некоторого алгоритма задается формулой

T(n) =  · T(n/k) + c·n^ ,

где k – целое число, k > 1

 < log_k,  > 0

 – обычное целое (хотя это необязательно),

то существует следующая оценка трудоемкости длинного алгоритма:

T(n) ≈ n log_k

Без доказательств.

Комментарии. Что делать, если происходит переполнение разрядов при вычислении по формуле (2.8)?

Предположим, что при сложении (при вычислении u) у нас получились не k, а (k+1)-разрядные числа, т.е. a и b имеют k+1 разряд.

Выделим старший разряд: a₁, b₁ = 0 или 1, но один из них обязательно равен 1. Тогда произведение можно осуществить следующим образом:

a·b = a₁b₁ · 2^2k + (a₁b₁ + a₂b₂) · 2^k + a₂b₂

флаг (0 или 1)

равно либо b₂, либо a₂, либо в худшем случае a₂+b₂

В случае, когда возникает переполнение, перемножение k+1 разрядных числе выполняется по формуле 2.10. В ней по-прежнему одно умножение (a₂b₂) и одно сложение, которое может и не понадобиться. На трудоемкости (рекуррентная формула 2.9) это существенно не отражается:

T(n) = 3 T(n/2) + 4n (2.9’)

или T(n) = 3 T(n/2) + 5n.

Согласно Теореме 2.2, на трудоемкости перемножения по формуле 2.8 (формула быстрого умножения) это не сказывается. Получаем:

T(n) ≈ n^log3 ≈n^1.58 << n²