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)