Деление чисел с фиксированной запятой в прямом и дополнительном кодах

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

В наиболее распространенных в настоящее время ЭВМ с системой команд X86 или IA-32 деление производится над числами с фиксированной точкой со знаком или без знака форматом байт или слово. При этом результат получается в виде целой части и остатка, причем каждая часть результата занимает фиксированное число байт.

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

делимое и делитель имеют равную длину в n разрядов (для чисел, заданных в прямом коде, эти разряды предназначены лишь для хранения модуля числа);

в случае, если делимое по абсолютной величине больше делителя, результат фиксируется как ±∞, где знак бесконечности определяется из соотношения знаков операндов;

если делимое по абсолютной величине меньше делителя, то результат получается так же n-разрядным, как и операнды; при этом проводится вычисление n+1 разряда результата с последующим округлением до n разрядов.

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

Деление чисел, заданных в прямом коде

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

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

Деление со сдвигом и автоматическим восстановлением остатка

На первом этапе проводится определение знака частного:

$$Зн.Z = Зн.X \oplus Зн.Y$$

Затем сравниваем абсолютные величины делимого и делителя.

α₀ = [|X| - |Y|]_дк

Если α₀ ≥ 0, то |X| ≥ |Y|. Следовательно, для чисел с фиксированной запятой Z = ∞, и дальнейшее деление не имеет смысла.

Если α₀ < 0, то очередные остатки при делении получаем по следующей рекуррентной формуле

$$\alpha_{i+1}=\begin{cases}2\alpha_i+\left| Y \right|, \text{ если } \alpha_i \lt 0\\2\alpha_i+\left| -Y \right|_{ДК}, \text{ если } \alpha_i\geq0\end{cases}$$

Очередные разряды мантиссы результата, начиная с z₁, вычисляются по формуле

$$z_i=\begin{cases}0,\text{ если } \alpha_i\lt0\\1,\text{ если } \alpha_i\geq0\end{cases}$$

Разряды результата получаются в прямом коде.

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

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

Пример 9.1

Выполнить деление двух чисел с фиксированной запятой, заданных в прямом коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_пк = 1.0110; Y_пк = 0.1010

Решение

$$ЗнZ = ЗнX \oplus ЗнY = 1 \oplus 0 = 1$$

Получив достаточное количество цифр в мантиссе, запишем окончательный результат:

Пример 9.2

Выполнить деление двух чисел с фиксированной запятой, заданных в прямом коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_пк = 0.1110; Y_пк = 1.1010.

Решение

$$ЗнZ = ЗнX \oplus ЗнY = 0 \oplus 1 = 1$$

Деление со сдвигом делителя и автоматическим восстановлением остатка

Анализ формул (9.1) и (9.2) показывает, что значение очередного разряда частного зависит от соотношения удвоенного значения остатка, полученного на предыдущем шаге, и модуля делителя.

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

α₀ = [|X| - |Y|]_дк

$$\alpha_{i+1}=\begin{cases}\alpha_i+\left| Y \right|\cdot 2^{-(i+1)}, \text{ если } \alpha_i\lt0\\\alpha_i+\left[\left| -Y \right|\cdot 2^{-(i+1)},\right]_{ДК}, \text{ если } \alpha_i\geq0\end{cases}$$ $$z_i=\begin{cases}0,\text{ если } \alpha_i\lt0\\1,\text{ если } \alpha_i\geq0\end{cases}$$

Анализируя формулу (9.3), можно сделать вывод, что схемотехнически реализация этого алгоритма потребует n-разрядного регистра для хранения модуля делимого, 2n-разрядного регистра для модуля делителя с учетом его сдвига в сторону младших разрядов, 2n-разрядного регистра для хранения остатка, комбинационные схемы для выполнения операции округления модуля частного, а также триггеры для хранения знаков операндов и результата.

Как и при выполнении операции умножения, деление без потери точности можно проводить в укороченной разрядной сетке длиной n+d разрядов, где d = log₂n и, соответственно, использовать регистры меньшей разрядности. Достоинства и недостатки такого подхода рассматривались при обсуждении алгоритмов умножения в предыдущей главе. В примерах мы будем использовать 2n-разрядную сетку.

Пример 9.3

Выполнить деление двух чисел с фиксированной запятой, заданных в прямом коде, по алгоритму деления со сдвигом делителя и автоматическим восстановлением остатка: X_пк = 0.1110; Y_пк = 1.1010.

Решение

$$ЗнZ = ЗнX \oplus ЗнY = 0 \oplus 1 = 1$$

Результат:

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

Пример 9.4

Выполнить деление двух чисел с фиксированной запятой, заданных в прямом коде, по алгоритму деления со сдвигом делителя и автоматическим восстановлением остатка: X_пк = 1.0011; Y_пк = 1.0110.

Решение

$$ЗнZ = ЗнX \oplus ЗнY = 1 \oplus 1 = 0$$

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

Таким образом, результат будет точно равен

Деление чисел, заданных в дополнительном коде

Для чисел с фиксированной запятой, заданных в дополнительном коде, алгоритмы деления во многом совпадают с алгоритмами деления для чисел, заданных в прямом коде. Назовем лишь имеющиеся отличия:

получаемый на начальном шаге деления нулевой остаток α₀ даёт возможность не только определить возможность продолжения деления для данного формата чисел, но и в случае удачного исхода определяет знак результата;

получаемые при делении остатки позволяют определить очередную цифру частного непосредственно в дополнительном коде;

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

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

Деление со сдвигом и автоматическим восстановлением остатка

Как отмечалось выше, при любом алгоритме деления получение очередного остатка связано со сложение двух чисел разных знаков. Так как при делении чисел, заданных в дополнительном коде, знак результата получается автоматически в процессе деления, то основные формулы (9.1) и (9.2) несколько изменяются по сравнению с делением чисел, заданных в прямом коде:

$$\alpha_0=\begin{cases}X_{ДК}+\left[Y\right]_{ДК},\text { если }ЗнX_{ДК}\neqЗн Y_{ДК}\\X_{ДК}+\left[-Y\right]_{ДК},\text { если }ЗнX_{ДК}=Зн Y_{ДК}\end{cases}$$

Если Зн α₀ = Зн X_дк, то |X| ≥ |Y|. Следовательно, для чисел с фиксированной запятой Z = ∞, и дальнейшее деление не имеет смысла.

Если Зн α₀ ≠ Зн X_дк, то очередные остатки при делении получаем по следующей рекуррентной формуле

$$\alpha_{i+1}=\begin{cases}2\alpha_i+\left[Y\right]_{ДК},\text { если }Зн\alpha_i\neqЗн \left[Y\right]_{ДК}\\2\alpha_i+\left[-Y\right]_{ДК},\text { если }Зн\alpha_i=Зн \left[Y\right]_{ДК}\end{cases}$$

Очередные разряды мантиссы результата, начиная с z₀, вычисляются по формуле

$$Z_{i ДК}=\begin{cases}0,\text{ если } Зн\alpha_i \neq Зн\left[Y\right]_{ДК}\\1,\text{ если } Зн\alpha_i = Зн\left[Y\right]_{ДК}\end{cases}$$

Пример 9.5

Выполнить деление двух чисел с фиксированной запятой, заданных в дополнительном коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_дк = 1.0111; Y_дк = 1.0110.

Решение

Результат

Пример 9.6

Выполнить деление двух чисел с фиксированной запятой, заданных в дополнительном коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_дк = 1.0111; Y_дк = 0.0110.

Решение

Деление со сдвигом делителя и автоматическим восстановлением остатка

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

Первый шаг проводится по формуле

$$\alpha_0=\begin{cases}X_{ДК}+\left[Y\right]_{ДК},\text { если }ЗнX_{ДК}\neqЗн Y_{ДК}\\X_{ДК}+\left[-Y\right]_{ДК},\text { если }ЗнX_{ДК}=Зн Y_{ДК}\end{cases}$$

На этом шаге, определяется, превышает ли модуль делимого модуль делителя и если нет, то определяется знак частного z₀, на основании следующего выражения:

$$Z_{i ДК}=\begin{cases}0,\text{ если } Зн\alpha_i \neq Зн\left[Y\right]_{ДК}\\1,\text{ если } Зн\alpha_i = Зн\left[Y\right]_{ДК}\end{cases}$$

Очередной остаток определяется следующим образом:

$$\alpha_{i+1}=\begin{cases}\alpha_i+\left[ Y \right]_{ДК}\cdot 2^{-(i+1)}, \text{ если } Зн\alpha_i \neq Зн\left[Y\right]_{ДК}\\\alpha_i+\left[\left| -Y \right|\right]_{ДК}\cdot 2^{-(i+1)}, \text{ если } Зн\alpha_i = Зн\left[Y\right]_{ДК}\end{cases}$$

По соотношению знака очередного остатка и знака [Y]_дк определяется очередная цифра частного согласно (9.10).

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

Пример 9.7

Выполнить деление двух чисел с фиксированной запятой, заданных в дополнительном коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_дк = 1.1110; Y_дк = 0.0011.

Решение

Результат

Пример 9.8

Выполнить деление двух чисел с фиксированной запятой, заданных в дополнительном коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_дк = 1.1100; Y_дк = 1.1000.

Решение

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

который явно не соответствует реальному.

Продолжим деление

Получаем окончательный результат:

то есть число, постепенно приближающееся к 2^-1, что и следовало ожидать из анализа значений делимого и делителя.

Рассмотрим аналогичную ситуацию для случая отрицательного результата.

Пример 9.9

Выполнить деление двух чисел с фиксированной запятой, заданных в дополнительном коде, по алгоритму деления со сдвигом и автоматическим восстановлением остатка: X_дк = 0.0010; Y_дк = 1.1000.

Решение

Получили ситуацию, аналогичную предыдущему примеру – нулевой остаток. Дополнение получившихся разрядов результата (1.10) нулями приведет к тому, что модуль результата будет равен 2^-1 (0.1000₂), в то время как он должен получиться равным 2^-2 (0.0100₂), так как |X| = 0.0010 и |Y| = 0.1000. Поэтому деление в данном случае также необходимо продолжить до получения необходимого количества цифр частного. Не проводя соответствующих выкладок (они аналогичны предыдущим примерам), запишем следующий результат:

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

Краткие итоги

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

Вопросы и задания

Назовите основные способы деления чисел с фиксированной запятой в прямом и дополнительном кодах.

Как связано количество разрядов частного с архитектурой конкретной ЭВМ?

Как связан результат, получаемый при делении чисел, заданных в прямом коде, с истинным результатом: всегда превышает его, всегда меньше него, нельзя сказать однозначно?

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

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

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

Какой из алгоритмов деления чисел, заданных в прямом коде, позволяет быстрее получить конечный результат?

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

Какой из алгоритмов более быстродействующий и требует меньше аппаратных затрат: алгоритм деления чисел, заданных в прямом коде или заданных в дополнительном коде?