Схемы ускоренного умножения

Для ускорения умножения разработан ряд алгоритмов, большой вклад в эти разработки внес Э. Бут (Е. Вооt). Рассмотрим процесс умножения по гак называемому модифицированному алгоритму Бута (умножение сразу на два разряда).

Из изложенного выше видно, что основную задержку в процесс выработки произведения вносит суммирование частичных произведений. Уменьшение их числа сократило бы время суммирования. К этому приводит алгоритм, основанный на следующих рассуждениях.

Пусть требуется вычислить произведение

Р = А х В = А х (b _n-₁ 2 ^{n - 1} + b _{n -2} 2 ^{n - 2} +…+b₀2⁰). (a)

Непосредственное воспроизведение соотношения (а) связано с выработкой частичных произведений вида (i = 0...n - 1). Число таких произведе­ний равно разрядности множителя n.

Выражение (а) можно видоизменить с помощью соотношения

, (б)

справедливость которого очевидна.

Это соотношение позволяет разреживать последовательность (спектр) сте­пеней в сумме частичных произведений. Можно, например, исключить чет­ные степени, как показано на рис. 2.39, а. Исключение четных (или нечет­ных) степеней не только изменяет значения оставшихся частичных произве­дений, но и сокращает их число примерно вдвое, что, в конечном счете, ус­коряет выработку произведения. Для того чтобы "разнести по соседям" член со степенью , расширим разрядную сетку, введя слагаемое

(нулевой разряд с номером -1).

Оставшиеся частичные произведения имеют вид

.

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

Рис- 2.39- К пояснению принципа быстрого умножения "срезу на два разряда" (в) и схема быстрого умножения (б)

Для всех возможных сочетаний b_i+1, b_i , b_i-1 можно составить таблицу (табл. 2.14) частичных произведений.