Классификация алгоритмов умножения

В основе нашего умения умножать числа лежит умение умножать положительные числа. Знаки сомножителей принимаются нами во внимание только при определении знака произведения. Поэтому ограничимся рассмотрением алгоритмов умножения чисел, представленных на РС без разряда знака, то есть чисел неотрицательных.

При умножении чисел с фиксированным положением позиционной точки от изменения ее положения относительно разрядов РС изменяется только ее положение относительно разрядов точного произведения. При этом последовательность цифр точного кода произведения остается неизменной:

1110. ´ 1100. = 10101000.

11.10 ´ 11.00 = 1010.1000

.1110 ´ .1100 = .10101000

Поэтому основные особенности алгоритмов умножения можно рассматривать, не принимая во внимание расположение позиционной точки относительно разрядов РС.

Любое дробное число, записанное конечным количеством цифр, можно интерпретировать как число целое, изменяя числовое значение единицы младшего разряда числа и не меняя (!) последовательности цифр в изображении числа.

12.340₁₀[км] = 12340₁₀[м];

12.34₁₀[единиц] = 1234₁₀[сотых долей единицы];

101.001₂[единиц] =101001₂[восьмых долей единицы];

1111110.0₂´2^-4= 1111110.₂[шестнадцатых долей]

Поэтому умножение дробных чисел можно свести к умножению целых чисел. Так и поступим.

Пример.Вычисление произведения C=A´B двоичных кодов.

Таблица 6.1

Номера разрядов сомножителей:

Множимое A:

Множитель B:

Номера частичных произведений

C =

Напомним основные термины, связанные с вычислением произведения A´B двух чисел:

- A – множимое;

- B – множитель;

- A и B – сомножители;

- произведение множимого на цифру множителя – частичное произведение.

Для ссылки на частичные произведения им естественно присвоить номера, совпадающие с номерами разрядов множителя, цифры которого использованы при вычислении частичного произведения.

Произведение вычисляется как сумма частичных произведений.

Со школы мы привыкли вычислять частичные произведения во временной последовательности, соответствующей направлению оси времени, показанному в таблице 6.1. Понятно, что сумма частичных произведений не изменится, если они будут вычисляться в прямо противоположной временной последовательности. Это наблюдение позволяет все алгоритмы умножения разделить на два класса в зависимости от того, какой из разрядов множителя используется первым при вычислении частичных произведений.

По последовательности обработки разрядов множителя все алгоритмы умножения делятся на 2 класса:

- умножение младшими разрядами вперед;

- умножение старшими разрядами вперед.

По содержимому таблицы 6.1 можно заметить, что каждое частичное произведение либо равно нулю, либо представляет собой сдвинутый влево код множимого. Причем, величина сдвига (количество разрядов, на которые код множимого сдвинут влево относительно своего начального состояния) всегда равна номеру частичного произведения. Такие сдвиги необходимы для правильного взаимного позиционирования разрядов частичного произведения и разрядов произведения. В примере правильное взаимное позиционирование достигается за счет сдвигов кода множимого влево. Но любое движение, как известно, относительно. Поэтому вместо сдвигов кода множимого влево можно использовать сдвиги разрядов произведения вправо. Эти соображения позволяют все алгоритмы умножения классифицировать по признаку «что сдвигается».

По способу достижения правильного взаимного расположения разрядов произведения и разрядов частичного произведения все алгоритмы умножения делятся на 2 класса:

- умножение со сдвигом множимого;

- умножение со сдвигом суммы частичных произведений.

Два рассмотренных критерия классификации алгоритмов умножения взаимно независимы, поэтому совместно они определяют четыре класса алгоритмов:

- умножение младшими разрядами вперед:

- со сдвигом множимого (влево);

- со сдвигом суммы частичных произведений (вправо);

- умножение старшими разрядами вперед:

- со сдвигом множимого (вправо);

- со сдвигом суммы частичных произведений (влево).

Дополнительные вариации в разнообразие алгоритмов вносит количество разрядов множимого, принимаемых во внимание одновременно.

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

- алгоритмы поразрядной обработки множителя;

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

- алгоритмы умножения на 3 разряда множителя одновременно;

- алгоритмы умножения на 4 разряда множителя одновременно.

Известны многочисленные вариации алгоритмов умножения, в которых приняты специальные меры для повышения их быстродействия при «прохождении» через цепочку единиц, следующих друг за другом в коде множителя. Акцентировать здесь внимание на всех подобных нюансах алгоритмов умножения не представляется возможным. Отдельному обсуждению подлежат алгоритмы, использующие технологию конвейерной обработки информации. Рассмотрение подобных вопросов выходит за рамки данного пособия.

Ограничимся рассмотрением алгоритмов поразрядной обработки множителя.

Специальному рассмотрению подлежат алгоритмы умножения, использующие обратные и дополнительные коды для представления сомножителей. Таким образом, вид кода (ПК, ОК или ДК), в котором представлены сомножители, можно использовать в качестве еще одного критерия классификации алгоритмов умножения.

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

Предыдущая 1 2 345 6 7 Следующая

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...