Scribd
Upload
3 views8 pages

Division

Uploaded by

Aadarsh Adarsh P P
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views8 pages

Division

Uploaded by

Aadarsh Adarsh P P
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

15CSE301 Computer

Architecture & Organization


Arithmetic Operation – Part 2
Divide: Paper &
Pencil
1001 Quotient
Divisor 1000 1001010 Dividend
–1000
10
101
1010
–1000
10 Remainder (or
Modulo result)

Dividend = Quotient × Divisor + Remainder


Restoring division hardware
Divisor on the left half of Divisor reg
Dividend on the right half of Rem reg
Start: Place Dividend in Remainder
Divide Algorithm - 1
•Takes n+1 steps for n-bit Quotient & Rem. 1. Subtract the Divisor register from the
Remainder Quotient Divisor Remainder register, and place the result
0000 0111 0000 0010 0000 in the Remainder register.

Remainder  0 Test Remainder < 0


Remainder

2a. Shift the 2b. Restore the original value by adding the
Quotient register Divisor register to the Remainder register, &
to the left setting place the sum in the Remainder register. Also
the new rightmost shift the Quotient register to the left, setting
bit to 1. the new least significant bit to 0.

3. Shift the Divisor register right1 bit.

n+1 No: < n+1 repetitions


repetition?
Yes: n+1 repetitions (n = 4 here)
2/12/03 ©UCBDone
Spring 2003
Example
Divide Algorithm I example (7 / 2)
Remainder QuotientDivisor
0000 0111 00000 0010 0000
1: 1110 0111 00000 0010 0000
2: 0000 0111 00000 0010 0000
3: 0000 0111 00000 0001 0000
1: 1111 0111 00000 0001 0000
2: 0000 0111 00000 0001 0000 Answer:
3: 0000 0111 00000 0000 1000
1: 1111 1111 00000 0000 1000 Quotient = 3
2: 0000 0111 00000 0000 1000 Remainder = 1
3: 0000 0111 00000 0000 0100
1: 0000 0011 00000 0000 0100
2: 0000 0011 00001 0000 0100
3: 0000 0011 00001 0000 0010
1: 0000 0001 00001 0000 0010
2: 0000 0001 00011 0000 0010
3: 0000 0001 00011 0000 0001

Instead of shifting divisor to right,


shift remainder to left?
DIVIDE HARDWARE 2
• 32-bit Divisor reg, 32 -bit ALU, 64-bit Remainder reg,
(0-bit Quotient reg)

Divisor
32 bits

32-bit ALU

“HI” “LO” Shift Left


Remainder (Quotient) Control
64 bits Write
Divide Algorithm 2
Step Remainder Div. Start: Place Dividend in Remainder
0 0000 0111 0010
1.1 0000 1110 1. Shift the Remainder register left 1 bit.
1.2 1110 1110
2. Subtract the Divisor register from the
1.3b 0001 1100 left half of the Remainder register, & place the
2.2 1111 1100 result in the left half of the Remainder register.
2.3b 0011 1000
Remainder ≥ 0 Test Remainder < 0
3.2 0001 1000 Remainder
3.3a 0011 0001
3a. Shift the 3b. Restore the original value by adding the Divisor
Remainder register register to the left half of the Remainder register,
to the left setting &place the sum in the left half of the Remainder
the new rightmost register. Also shift the Remainder register to the
bit to 1. left, setting the new least significant bit to 0.

4.2 0001 0001 nth No: < n repetitions


repetition?
4.3a 0010 0011
Yes: n repetitions (n = 4 here)
0001 0011 Done. Shift left half of Remainder right 1 bit

You might also like