4.12. СПОСОБЫ УСКОРЕННОГО ДЕЛЕНИЯ

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

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

Пример. Будем считать для простоты, что операнды заданы в виде целых чисел:

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

Правомерность подобного изменения алгоритма деления основывается на том факте, что остаток после выполнения шагов обычного алгоритма деления при совпадении к старших цифр остатка и делителя В определится как

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

Пример. Заданы обычное; б) ускоренное деление

Таблица 4.5

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

Развитием первого способа ускорения деления является способ, по которому всегда одновременно определяются две цифры частного.

Если А — делимое; делитель, то на основании (4.22) для остатка справедливо:

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

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

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

Тогда коррекция остатка производится следующим образом. Если раньше проверялось условие

где то теперь должно проверяться эквивалентное ему условие

Таблица 4.6

Окончательные правила проверки условий представлены в табл. 4.6.

В тех случаях, когда в ЭВМ обеспечивается большая скорость выполнения операции умножения, может оказаться целесообразным вместо операции деления применить один из итеративных способов определения частного, основанных на использовании операций только сложения и умножения. В отличие от способов деления, рассмотренных выше, методы, использующие умножение, на каждой итерации уточняют приближение, а не определяют очередную цифру частного. Один из наиболее простых способов этой группы сводится к серии итераций, в каждой из которых делимое и делитель умножаются на один и тот же множитель, в результате чего частное не изменяется. Целью этих итераций является преобразование делителя, первоначально равного В, а в конце итерации — в число, отличающееся от единицы не более чем на единицу младшего разряда. Если для этого потребуется итераций, то делимое А, а в конце итерации — по окончании итерации будет с точностью до младшего разряда равно частному , т. е.

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

т. е.

где

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

В качестве множителя для итерации выбирают

который с учетом (4.31) равен

В результате умножения получим для делителя в конце итерации новое значение

Из (4.32) и (4.33) следует, что

т. е.

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

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

Ускорение операции деления может быть также достигнуто путем выполнения устройства для деления в виде итеративной сети, простейшая модификация которой показана на рис. 4.14 [15].

Каждый элемент сети (рис. 4.14) содержит сумматор и элемент «исключающее реализующий функцию и управляющий вводом делителя В в сумматор (рис. 4.15).

Шестиразрядное делимое трехразрядный делитель и

Рис. 4.14

Рис. 4.15

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