logo
tsvpis

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

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

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

Тогда xy = v 22k+(u – v – w)2k + 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

< logk, > 0

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

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

T(n) ≈ n logk

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

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

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

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

a·b = a1b1 · 22k + (a1b1 + a2b2) · 2k + a2b2

флаг (0 или 1)

равно либо b2, либо a2, либо в худшем случае a2+b2

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

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

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

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

T(n) ≈ nlog3 ≈n1.58 << n2