Page 37 - ЭВМ
P. 37
Оценка среднего числа «+» и «–» при выполнении операций по
методу Лемана проводится следующим образом.
Пусть n – число разрядов сомножителя. Пусть p i – вероятность
того, что будет выполняться действие на i шаге. Пусть значения раз-
рядов b i «1» или «0» равновероятны (½).
В соответствии с формулой для параметра d i, определяющего
действие сложения-вычитания, имеем следующее:
1
p = i (1 p− i− 1 ) , i = 1.
2
Откуда
p 0 = 0; p 1 = 1/2; p 2 = 1/4; p 3 = 3/8; p 4 = 5/8.
Тогда:
1
p = lim p = i (1 p− );
i→∞ 2
p = 1/2(1 – p); 3/2p = 1/2, p = 1/3.
Отсюда среднее число действий при умножении по Леману
примерно равно n/3, а при обычном умножении равно n/2.
Проведем одновременный анализ нескольких разрядов множителя.
Ускоренное умножение за счёт одновременного анализа фикси-
рованного числа разрядов k на каждом шаге умножения рассмотрим
для случая k = 2.
Разбиваем множитель на группы по k разрядов справа налево.
37
