Формализация алгоритмов поразрядного умножения

Алгоритмы умножения будем рассматривать для n разрядной РС, предназначенной для отображения целых чисел без знака. Обозначим такую РС как РСЦБЗ_n.

В произведении A´B множитель B представим в виде (6.1):

B = å(b_i2ⁱ) = b_n-12^n-1 + b_n-22^n-2 +...+ b₂2² + b₁2¹ +b₀2⁰ (6.1)

Простейшие алгоритмы поразрядного умножения можно получить на основе тождественных преобразований выражения (6.2):

A´B = A´å(b_i2ⁱ) (6.2)

Вариант 1 тождественных преобразований выражения (6.2):

A´B = A´å(b_i2ⁱ) = å(A´b_i2ⁱ) = å(A´2ⁱ)b_i =

= (A´2 ^n-1)b_n-1+ (A´2 ^n-2)b_n-2+...+(A´2 ²)b₂+(A´2 ¹) b₁+(A´2 ⁰)b₀ (6.3)

Обозначим:

A_i = A´2ⁱ – это двоичный код A, сдвинутый влево на i разрядов.

Тогда:

A₀ = A;

A_i+1 = A_i´2 = L1(A_i· 0); (6.4)

A_i-1 = A_i/2 = R1(0 · A_i-1), для i > 0,

где · - символ операции конкатенации (склеивания) кодов;

- Lm обозначает операцию сдвига кода влево (Left) на m разрядов;

- Rm обозначает операцию сдвига кода вправо (Right) на m разрядов.

Вычисляя слагаемые выражения (6.3) с учетом (6.4) в том порядке как они записаны (слева - направо), мы реализуем алгоритм умножения старшими разрядами вперед со сдвигом множимого вправо:

A´B = ((…((A _n-1 b_n-1)+ A _n-2 b_n-2)+...+A₂ b₂)+A₁ b₁ )+A₀ b₀ (6.5)

Вычисления слагаемых выражения (6.3) в порядке обратном (то есть справа - налево) реализует алгоритм умножения младшими разрядами вперед со сдвигом множимого влево:

A´B = (A_n-1 b_n-1+(A _n-2 b_n-2+(...+(A₂ b₂+(A₁ b₁+(A₀ b₀ )))…))) (6.6)

Алгоритм 6.1. Поразрядное умножение старшими разрядами вперед со сдвигом множимого вправо.

Алгоритм следует из выражения (6.5). Рассмотрим простейший его вариант.

Даны: коды A и B чисел на РСЦБЗ_n.

Требуется вычислить произведение C=A´B.

Обозначим:

i – количество обработанных разрядов кода множителя.

1. Подготовка переменных:

1.1. C:= 0 (- подготовка к накапливанию суммы)

1.2. A:= Lm(A· 0…0), где m = n-1 (- сдвиг кода множимого влево на n-1 разряд с занесением в разрядную сетку нулей справа)

1.3. i := 0 (- пока не обработано ни одного разряда кода множителя)

2. Циклическая часть алгоритма:

2.1. Если b_n-1=1 (- проверка старшего разряда множителя),
то C:= C+A

2.2. B := L1(B); (- сдвиг кода множителя влево на 1 разряд)

A := R1(0· A); (- сдвиг кода множимого вправо на 1 разряд)

i := i+1 (- обработан еще один разряд кода множителя)

2.3. Если i < n,

то (- не все разряды множителя обработаны) перейти к 2.1.

3. Конец алгоритма (Код C задает искомое произведение)

Отметим основные недостатки алгоритма 6.1.

Алгоритм 6.2. Поразрядное умножение младшими разрядами вперед со сдвигом множимого влево.

Алгоритм следует из (6.6). Рассмотрим простейший его вариант.

Даны: коды A и B чисел на РСЦБЗ_n.

Требуется вычислить произведение C=A´B.

Обозначим:

i – количество обработанных разрядов кода множителя.

1. Подготовка переменных:

1.1. C := 0 (- подготовка к накапливанию суммы)

1.2. i := 0 (- пока не обработано ни одного разряда кода множителя)

2. Циклическая часть алгоритма:

2.1. Если b₀ =1, (- проверка младшего разряда множителя)

то C := C+A

2.2. B := R1(B); (- сдвиг кода множителя вправо на 1 разряд)

A := L1(A· 0); (- сдвиг кода множимого влево на 1 разряд)

i := i+1 (- обработан еще один разряд кода множителя)

2.3. Если i < n,

то (- не все разряды множителя обработаны) перейти к 2.1

3. Конец алгоритма (Код C задает искомое произведение)

Недостатки алгоритма 6.2 совпадают с отмеченными недостатками алгоритма 6.1. Здесь, по аналогии с алгоритмом 6.1, замена операции B:= R1(B) на операцию B:= R1(0· B) позволяет увеличить быстродействие алгоритма за счет его досрочного завершения по признаку B = 0.

Заметим, что оба рассмотренных алгоритма можно ускорить, приняв во внимание возможное нулевое значение каждого из сомножителей. Такой анализ разумно проводить после присвоения переменной C начального значения, равного нулю, то есть после шага 1.1 обоих алгоритмов.

Вариант 2 тождественных преобразований выражения (6.2).

Обозначим:

P_i = A´ b_i. (6.7)

Тогда выражение (6.2) можно преобразовать к виду (6.8):

A´B = A´å(b_i2ⁱ) = å(A´b_i2ⁱ) = åP_i2ⁱ =

= P_n-1´2 ^n-1 +P_n-2´2 ^n-2+...+P₂´2 ²+P₁´2 ¹+P₀ (6.8)

Вынесением за скобки общих множителей равных 2, выражение (6.8) преобразуем к виду (6.9):

A´B = åP_i2ⁱ = ((…((0´2+P_n-1)´2 +P_n-2)´2+...+P₂)´2+P₁)´2+P₀ (6.9)

Последовательность действий, определяемую выражением (6.9), следует понимать такой:

- начальное значение накопленной суммы равно 0;

- накопленная сумма умножается на 2 сдвигом влево на один разряд;

- к результату сдвига прибавляется очередное произведение P_i.

Вычисление произведения A´B по выражению (6.9) реализует алгоритм умножения старшими разрядами вперед со сдвигом накопленной суммы частичных произведений влево.

При разработке алгоритма 6.3 умножения учтем, что, как следует из (6.7), P_i=0, если b_i=0, и P_i= A, если b_i= 1.

Алгоритм 6.3. Поразрядное умножение старшими разрядами вперед со сдвигом суммы частичных произведений влево.

Алгоритм следует из (6.9). Рассмотрим простейший его вариант.

Даны: коды A и B чисел на РСЦБЗ_n.

Требуется вычислить произведение C=A´B.

Обозначим:

i – количество обработанных разрядов кода множителя.

1. Подготовка переменных:

1.1. C := 0 (- подготовка к накапливанию суммы)

1.2. i := 0 (- пока не обработано ни одного разряда кода множителя)

2. Циклическая часть алгоритма:

2.1. C:= L1(C· 0) (- сдвиг накопленной суммы влево на 1 разряд)

2.2. Если b_n-1=1, (- проверка старшего разряда множителя)

то C:= C+A

2.3. B := L1(B); (- сдвиг кода множителя влево на 1 разряд)

i := i+1 (- обработан еще один разряд кода множителя)

2.4. Если i < n,

то (- не все разряды множителя обработаны) перейти к 2.1

3. Конец алгоритма (Код C задает искомое произведение)

Отметим некоторые особенности алгоритма 6.3.

Вариант 3 тождественных преобразований выражения (6.2).

Выражение (5.2) можно преобразовать к следующему виду:

A´B = A´å(b_i2ⁱ) =A´å(2^n-1´b_i2^-(n-1)+i) = å( A´2^n-1´b_i´2^-(n-1)+i) (6.10)

Обозначим:

P_i = A´2^n-1´ b_i. (6.11)

Тогда выражение (6.10) можно преобразовать к виду (6.12):

A´B = å(P_i´2^-(n-1)+i) =

= P_n-1´2 ⁰+P_n-2´2 ^-1+...+P₂´2^–(n-3)+P₁´2^–(n-2)+P₀´2^–(n-1) (6.12)

В выражении (6.12) вынесем за скобки общие множители равные 2^-1:

A´B=P_n-1+(P_n-2+...+(P₂+(P₁+(P₀+0´2^–1)´2^–1)´2^–1)´2^–1…)´2^–1 (6.13)

Как видно, в (6.13) после прибавления последнего слагаемого, равного P_n-1, операция умножения на 2^–1 не выполняется. Поэтому последовательность действий, задаваемую выражением (1.46), следует понимать такой:

- начальное значение накопленной суммы произведений равно 0;

- накопленная сумма произведений умножается на 2^–1, то есть сдвигается вправо на один разряд;

- к результату сдвиг прибавляется очередное (i возрастает) произведение P_i.

Именно в соответствии с таким пониманием последовательности действий и с целью исключения особого случая обработки произведения P₀ во внутренних скобках выражения (6.13) вставлено слагаемое равное 0´2^–1.

Вычисление произведения A´B по выражению (6.13) реализует алгоритм умножения младшими разрядами вперед со сдвигом накопленной суммы частичных произведений вправо.

При разработке алгоритма 1.12 умножения учтем, что, как следует из (1.44), P_i=0, если b_i=0, и P_i= A´2^n-1, если b_i= 1.

Алгоритм 6.4. Поразрядное умножение младшими разрядами вперед со сдвигом суммы частичных произведений вправо.

Алгоритм следует из выражения (6.13). Рассмотрим простейший его вариант, учитывая, что операция A´2^n-1 эквивалентна сдвигу кода A влево на n-1 разряд.

Даны: коды A и B чисел на РСЦБЗ_n.

Требуется вычислить произведение C=A´B.

Обозначим:

i – количество обработанных разрядов кода множителя.

1. Подготовка переменных:

1.1. C:= 0 (- подготовка к накапливанию суммы)

1.2. A:= Lm(A· 0…0), где m = n-1 (- сдвиг кода множимого влево на n-1 разряд с занесением в разрядную сетку нулей)

1.3. i := 0 (- пока не обработано ни одного разряда кода множителя)

2. Циклическая часть алгоритма:

2.1. C := R1(0· C); (- сдвиг суммы вправо на 1 разряд)

2.2. Если b₀ =1, (- проверка младшего разряда множителя)

то C:= C+A

2.3. B := R1(B); (- сдвиг кода множителя вправо на 1 разряд)

i := i+1 (- обработан еще один разряд кода множителя)

2.4. Если i < n,

то (- не все разряды множителя обработаны) перейти к 2.1

3. Конец алгоритма (Код C задает искомое произведение)

Отметим основные особенности алгоритма 6.4.

1. Код произведения C представляется на РС двойной длины, то есть на РСЦБЗ_2n, и имеет вид C = c_2n-1c_2n-2…c_n-1c_n-2…c₁c₀.

2. Перед суммированием в результате шага 2.1 алгоритма старшая цифра c_2n-1 кода C становится равной нулю. Поэтому в операции суммирования участвует код C следующей структуры:

C = 0c_2n-2…c_n-1c_n-2…c₁c₀.

3. Слагаемое A в операции накапливания суммы C:= C+A после операции A:= Lm(A· 0…0), выполненной на шаге 1.2 алгоритма, имеет следующую структуру: A = 0a_2n-2…a_n-10…0.

Как следует из структур слагаемых, в операции накапливания суммы участвуют коды, показанные в таблице 6.3:

Таблица 6.3

Как видно из содержимого таблицы 6.3 младшие разряды кода суммы можно получить простым переписыванием соответствующих разрядов слагаемого C. Поэтому складывать необходимо только n разрядные составляющие кодов слагаемых: c_2n-2…c_n-1 и a_2n-2…a_n-1. Этот факт используется при проектировании аппаратной реализации рассматриваемого алгоритма. При этом для выполнения суммирования используется суммирующее устройство (сумматор) с n разрядными кодами слагаемых, а шаг 1.2 рассматриваемого алгоритма реализуется за счет того, что цифра a₀ исходного кода множимого складывается с цифрой c_n-1 кода C. Поэтому операция A:= Lm(A· 0…0) из шага 1.2 оказывается выполненной автоматически без выполнения шагов сдвига кода A.