DIVISION
The reciprocal operation of multiply is divide, an operation that is even less frequent and even more quirky.
It even offers the opportunity to
perform a mathematically invalid operation: dividing by 0. The example is
dividing 1,001,010 by 1000. The two operands (dividend and divisor) and the
result (quotient) of divide are accompanied by a second result called the
remainder. Here is another way to express the relationship between the
components:
Fig. 2.8
First version of the Division hardware
Dividend
= Quotient * Divisor + Remainder
where the remainder is smaller
than the divisor. Infrequently, programs use the divide instruction just to get
the remainder, ignoring the quotient. The basic grammar school division
algorithm tries to see how big a number can be subtracted, creating a digit of
the quotient on each attempt. Binary numbers contain only 0 or 1, so binary
division is restricted to these two choices, thereby simplifying binary
division. If both the dividend and divisor are positive and hence the quotient
and the remainder are nonnegative. The division operands and both results are
32-bit values.
A Division Algorithm and Hardware
Initially, the 32-bit Quotient
register set to 0. Each iteration of the algorithm needs to move the divisor to
the right one digit, start with the divisor placed in the left half of the
64-bit Divisor register and shift it right 1 bit each step to align it with the
dividend. The Remainder register is initialized with the dividend. Figure shows
three steps of the first division algorithm.
Unlike a human, the
computer isn’t smart enough to know in advance whether the divisor is
smaller than the dividend. It must first subtract the divisor in step 1; If the
result is positive, the divisor was smaller or equal to the dividend, so
generate a 1 in the quotient (step 2a). If the result is negative, the next
step is to restore the original value by adding the divisor back to the
remainder and generate a 0 in the quotient (step 2b). The divisor is shifted
right and then iterate again. The remainder and quotient will be found in their
namesake registers after the iterations are complete.
The following figure shows three
steps of the first division algorithm. Unlike a human, the
computer isn’t smart enough to know in advance whether the divisor is smaller
than the
dividend.
Fig. 2.9
Division Algorithm
It must first subtract the
divisor in step 1; remember that this is how we performed the comparison in the
set on less than instruction. If the result is positive, the divisor was
smaller or equal to the dividend, so we generate a 1 in the quotient (step 2a).
If the result is negative, the next step is to restore the original value by
adding the divisor back to the remainder and generate a 0 in the quotient (step
2b). The divisor is shifted right and then we iterate again. The remainder and
quotient will be found in their namesake registers after the iterations are
complete.
Using a 4-bit version of the
algorithm to save pages, let’s try dividing 710 by 210,
or 0000 01112 by 00102.
Fig. 2.10
Values of register in division algorithm
The above figure shows the value
of each register for each of the steps, with the quotient being 3ten and the
remainder 1ten. Notice that the test in step 2 of whether the remainder is
positive or negative simply tests whether the sign bit of the Remainder register
is a 0 or 1. The surprising requirement of this algorithm is that it takes n +
1 steps to get the proper quotient and remainder.
This algorithm and hardware can
be refined to be faster and cheaper. The speedup comes from shifting the
operands and the quotient simultaneously with the subtraction. This refinement
halves the width of the adder and registers by noticing where there are unused
portions of registers and adders.
SIGNED DIVISION
The one complication of signed
division is that we must also set the sign of the remainder. Remember that the
following equation must always hold:
Dividend = Quotient × Divisor + Remainder
To understand
how to set the sign of the remainder, let’s look at the example of dividing all
the
combinations of ±7 10 by ±2 10.
The first case is easy:
+7 ÷ +2: Quotient = +3, Remainder
= +1 Checking the results:
7 = 3 × 2 + (+1) = 6 + 1
If we change the sign of the dividend, the quotient must
change as well:
–7 ÷ +2: Quotient =
–3
Rewriting our basic formula to calculate the remainder:
Remainder = (Dividend – Quotient
× Divisor) = –7 – (–3 × +2) =
–7–(–6) = –1
So,
–7 ÷ +2: Quotient =
–3,
Remainder = –1
Checking the results again:
–7 = –3 × 2 + (
–1)
=
– 6
– 1
The following figure shows the revised hardware.
Fig. 2.11
Division hardware
The reason the answer
isn’t a quotient of –4 and a remainder of +1, which would also fit this
formula,
is that the absolute value of the quotient would then change depending on the
sign of the dividend and the divisor! Clearly, if
programming would be an even
greater challenge. This anomalous behavior is avoided by following the rule
that the dividend and remainder must have the same signs, no matter what the
signs of the divisor and quotient. We calculate the other combinations by
following the same rule:
Thus the correctly signed
division algorithm negates the quotient if the signs of the operands are
opposite and makes the sign of the nonzero remainder match the dividend.
Faster Division
Many adders can be used to speed
up multiply, cannot be used to do the same trick for divide. The reason is that
it is needed to know the sign of the difference before performing the next step
of the algorithm, whereas with multiply we could calculate the 32 partial
products immediately.
There are techniques to produce
more than one bit of the quotient per step. The SRT division technique tries to
guess several quotient bits per step, using a table lookup based on the upper
bits of the dividend and remainder. It relies on subsequent steps to correct
wrong guesses. A typical value today is 4 bits. The key is guessing the value
to subtract. With binary division, there is only a single choice.
These algorithms use 6 bits from
the remainder and 4 bits from the divisor to index a table that determines the
guess for each step. The accuracy of this fast method depends on having proper
values in the lookup table.
Restoring and non restoring division algorithm
•Assume ─ X register k-bit
dividend
• Assume
─ Y the k-bit divisor
• Assume
─ S a sign-bit
1. Start:
Load 0 into accumulator k-bit A and dividend X is loaded into the k-bit
quotient register MQ.
2. Step A :
Shift 2 k-bit register pair A -MQ left
3. Step B:
Subtract the divisor Y from A.
4. Step C:
If sign of A (msb) = 1, then reset MQ 0 (lsb) = 0 else set = 1.
5. Steps D:
If MQ 0 = 0 add Y (restore the effect of earlier subtraction).
6.
Steps A to D repeat again till the total number of
cyclic operations = k. At the end, A has the remainder and MQ has the
Fig. 2.12
Division of 4-bit number by 7-bit dividend
Division using Non-restoring Algorithm
•
Assume ─ that there is an accumulator
and MQ register, each of k-bits • MQ 0, (lsb of
MQ) bit gives
the quotient, which is saved after a subtraction or addition
•
Total number of additions or
subtractions are k-only and total number of shifts = k plus one
addition
for restoring remainder if needed
• Assume
─ that X register has (2 k−1) bit for dividend and Y has the k-bit
divisor
• Assume
─ a sign-bit
S shows the sign
1. Load
(upper half k −1 bits of the dividend X) into accumulator k-bit A
and load dividend X (lower half bits into the lower k bits at quotient register
MQ
• Reset
sign S = 0
• Subtract
the k bits divisor Y from S-A (1 plus k bits) and assign MQ 0 as per S
2. If sign
of A, S = 0, shift S plus 2 k-bit register pair A-MQ left and subtract the k
bits divisor Y from S-A (1 plus k bits); else if sign of A, S = 1, shift S plus
2 k-bit register pair A - MQ left and add the divisor Y into S-A (1 plus k
bits)
• Assign MQ 0 as per
Fig. 2.13
Division using Non-restoring Algorithm
3. Repeat
step 2 again till the total number of operations = k.
4. If at the
last step, the sign of A in S = 1, then add Y into S -A to leave the correct
remainder into A and also assign MQ 0 as per S, else do nothing.
5. A has the
remainder and MQ has the quotient
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.