This document discusses different techniques for performing integer division in computers, including iterative division methods like restoring and non-restoring division. It covers handling cases where the divisor has leading zero bits and the need for an extra bit in the accumulator. Complete algorithms for restoring and non-restoring division are provided.
This document discusses different techniques for performing integer division in computers, including iterative division methods like restoring and non-restoring division. It covers handling cases where the divisor has leading zero bits and the need for an extra bit in the accumulator. Complete algorithms for restoring and non-restoring division are provided.
This document discusses different techniques for performing integer division in computers, including iterative division methods like restoring and non-restoring division. It covers handling cases where the divisor has leading zero bits and the need for an extra bit in the accumulator. Complete algorithms for restoring and non-restoring division are provided.
This document discusses different techniques for performing integer division in computers, including iterative division methods like restoring and non-restoring division. It covers handling cases where the divisor has leading zero bits and the need for an extra bit in the accumulator. Complete algorithms for restoring and non-restoring division are provided.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 15
1
ECE 366 Computer Architecture
Instructor: Shantanu Dutt Department of Electrical and Computer Engineering University of Illinois at Chicago
Radix division is essentially a trial-and-error process, in which the next quotient bit is chosen from Example:
Binary division is much simpler, since the next quotient bit is either a 0 or 1 depending on whether the partial remainder is less than or greater than/equal to the divisor, respectively Integer division: Given 2 integers the dividend and the divisor, we want to obtain an integer quotient and an integer remainder , s.t.
IntegerFP division: Given 2 integers
the dividend and
the divisor,
we want to obtain a oating-point (FP) or real quotient
s.t.
We will talk about division of unsigned numbers rst
c Shantanu Dutt, UIC
Division SHR-Divisor Method
Start subtraction of from left most position of subtraction every iteration Pencil-paper division example:
; SHR
for next
c Shantanu Dutt, UIC
Division SHL-Partial-Remainder Method
Instead of shifting the divisor right by 1 bit, the partial remainder can be shifted left by one bit Example:
c Shantanu Dutt, UIC
Division Handling
with 0s in High-Order Bits
Another Example: Some higher order bits of the -bit divisor
are 0s:
Note that is stored as a 4-bit # (0010) in the computer. The type of manual adjustment done in the above example of converting 4-bit subtractions into 2-bit ones (in general, -bit subtractions to -bit ones, where ) is not possible in a computer
c Shantanu Dutt, UIC
Division Handling Problem with Two ways to tackle the problem: Method 1: Shift to the left by division for steps for an integer Example:
with 0s in High-Order Bits (contd.)
having higher order bits as 0s:
bits (until its MSB is a 1), do the (more steps for a FP )
c Shantanu Dutt, UIC
Division Handling Problem with
with 0s in High-Order Bits (contd.)
having higher order bits as 0s:
Method 2: Augment to the left by bits that are all 0s. Perform division for steps for an integer and more steps for a FP Example:
This is the type of division algorithm used in a computer
c Shantanu Dutt, UIC
Division A Caveat
Example for needing an extra bit to the left of the dividend to catch a 1 on a shift left (required when originally has more bits than (e.g., dividing an 8-bit number by a 6-bit one):
Thus need an extra bit in AC is to catch a 1 out of AC when the MSBs of the partial remainder and are both 1s but !
10
The adder/subtracter thus also needs to be bits; see block diagram of divider given next. NOTE: The extra bit is never required when both and have the same
number of bits to start with (this does not count the added later to ).
From Control Unit Dividend D Accumulator Q 1 17 XOR
Divisor V M
17
17
C out 1 17
17bit Add/Sub 1 From Control Unit
Serial division for 16bit unsigned numbers
#
1. To compute , store in the register, in the register and 0 in AC (Accumulator), and 0 in (holds the quotient bit before the shift and are -bit left). Note that is an -bit register, while ones, with 0s initially in their th bits. Repeat the following steps times: 2. Shift AC-Q-T register combination left 1 bit (initially, this has the effect of adding on 0s to the left of the dividend) (subtract divisor from -bit partial remainder 3. Perform ) " $ # % & ' % % ( & & ' (
'
12
4. If the result is negative, set , otherwise set 5. If the result of step 2 is negative, restore the old value of AC by doing $ $ % & % &
NOTE: Notice similarity between hardware for A&S multiplication and division. The same hardware with additional control can be used for both purposes.
c Shantanu Dutt, UIC
12
13
Division Complete Algorithm # 2
Non-restoring division algorithm: An extra addition step is needed in the previous algorithm to restore the old value of when the result of a subtraction is negative. This step is eliminated in non-restoring division: %
1. Same initialization as before. Repeat the following steps times: 2. Shift AC-Q-T register combination left 1 bit 3. If current Q[0] is 0 and this is not the 1st iteration then perform else perform 4. If the result is negative, set , otherwise set % & % & % & % & $ $
&
0 0
This works because: Let be the contents of register AC-Q at the beginning of the th iteration. After a SHL and subtraction, is computed. ) is -ve, restoration and then anIn restoring division: If this result ( )
other subtraction in the next iteration gives us
. 1
14
In non-restoring division: If the result of the previous iteration (
) ' (
) is 0
th iteration we perform a SHL to get -ve, we do not restore but in the and then add to get . This gives us the same result in AC-Q as in restoring division, and based on this same result we determine the next bit of the quotient. Thus non-restoring division will give us the same quotient as restoring division, though faster. Thus non-restoring division works correctly since restoring division is correct. 0 1
c Shantanu Dutt, UIC
14
15
Twos Complement Division (contd.)
There are no simple division algorithms for 2s complement #s unlike the case for multiplication This is primarily due to the difculty in selecting the quotient bits in such a way that it has tthe correct +ve or -ve 2s complement representation Thus the approach generally followed is to negate a -ve or , perform division and then negate the quotient if only one of or was -ve A more efcient division algorithm for 2s complement #s is the SRT method (for Sweeney, Robertson and Tocher, its inventors); see Ref. text # 1 (Hennesey and Patterson) for this algorithm if interested
