Division method Non Restoring.ppt

Non-restoring division is a binary division algorithm used to divide one binary number by another. Unlike traditional division, which is based on restoring the dividend, non-restoring division does not restore the dividend to its original value. Instead, it uses a non-restoring method to find the quotient.

1. Computer Organization
and Architecture
Topic: Division Non-Restoring
Method
by
Upendra Mishra
(M. Tech., Ph.D.*)
KIET Group of Institutions

2. Prerequisites
ShiftingofBits(LeftorRight)
Addition
Subtraction
2’sComplement

3. Divisionofunsigned binary integers
PaperPencilmethod
Example:
(Dividend)10/(Divisor)4=(Quotient)2; (Remainder)2
DividendDivisor Quotient
Remainder
4 10 2
8
2

4. Divisionofunsignedbinaryintegersis
instructivemethod.Therearetwomethods:
RestoreMethod
Non-RestoreMethod
Division ofunsigned binary integers

6. Flowchart for Unsigned
Binary Division-
Non-Restore Method
start
nnoof bits
M Divisor
A 0
Q Dividend
A < 0
Shift left AQ
A= A + M
Shift left AQ
A= A -M
A < 0
Q[0] = 0 Q[0] = 1
n=n-1
n=0
A < 0
Stop
A=A+M
Yes
No
Yes
No
No
NoYes
Yes

7. Flowchart for Unsigned
Binary Division-
Non-Restore Method
start
nnoof bits
M Divisor
A 0
Q Dividend
A < 0
Shift left AQ
A= A + M
Shift left AQ
A= A -M
A < 0
Q[0] = 0 Q[0] = 1
n=n-1
n=0
A < 0
Stop
A=A+M
Yes
No
Yes
No
No
NoYes
Yes

8. Division by Non-Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
N M A Q ACTION
4 00011 00000 1011 Start
00001 011_ Left shift AQ
11110 011_ A=A-M
3 11110 0110 Q[0]=0
11100 110_ Left shift AQ
11111 110_ A=A+M
2 11111 1100 Q[0]=0
11111 100_ Left Shift AQ
00010 100_ A=A+M
1 00010 1001 Q[0]=1
00101 001_ Left Shift AQ
00010 001_ A=A-M
0 00010 0011 Q[0]=1
start
nnoof bits
M Divisor
A 0
Q Dividend
A < 0
Shift left AQ
A= A + M
Shift left AQ
A= A -M
A < 0
Q[0] = 0 Q[0] = 1
n=n-1
n=0
A < 0
Stop
A=A+M
Yes
No
Yes
No
No
NoYes
Yes
M = 00011
M’ = 11100
M’+1 = 11101
-M = 11101
-M = 11101

9. Division by Non-Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
N M A Q ACTION
4 00011 00000 1011 Start
00001 011_ Left shift AQ
11110 011_ A=A-M
3 11110 0110 Q[0]=0
11100 110_ Left shift AQ
11111 110_ A=A+M
2 11111 1100 Q[0]=0
11111 100_ Left Shift AQ
00010 100_ A=A+M
1 00010 1001 Q[0]=1
00101 001_ Left Shift AQ
00010 001_ A=A-M
0 00010(2)(R) 0011(3)(Q) Q[0]=1
start
nnoof bits
M Divisor
A 0
Q Dividend
A < 0
Shift left AQ
A= A + M
Shift left AQ
A= A -M
A < 0
Q[0] = 0 Q[0] = 1
n=n-1
n=0
A < 0
Stop
A=A+M
Yes
No
Yes
No
No
NoYes
Yes

10. 10
Question
•Try dividing 13/4and 15/3

11. 11
Divide Overflow
Condition:
1. The number of bits in dividend is twice as the number of bits in the divisor. AND
2. The higher order half bits of the dividend have a value more than or equal to the value of the
total bits of the divisor.
OR
1. The divide overflow also checks that whether the divisor is zero or not.
•All these conditions are checked before the division process starts.
•Let dividend(Q) = 1010 1100 (length 8 bit)
Divisor(M) is 0111 (length 4 bit)
Here, the number of bits in Q is twice the number of bits in M
Higher order half bits of Q is 1010 value 10
total bits value of M is 0111 value 7 so Q>M
OR check whether M is 0000 or not
if yes also indicate Divide Overflow

12. 12
Reference
1.Computer System Architecture -Morris Mano
2.William Stallings, Computer Organization and Architecture-Designing for Performance,
Pearson Education, Seventh edition, 2006.

13. Thank
You

14. Thank
You

15. Division by Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
Start
nnoof bits
M Divisor
A 0
Q Dividend
Shift left AQ
A= A -M
MSB
of A
Q[0] = 1
Q[0] = 0
Restore A
n = n-1
Is n = 0
Quotient in Q
Remainder in A
Stop
=1=0
Yes
No
nM A Q Operation
400011 (3)00000 (0)1011 (11)initialize
00011 00001 011_ shift left AQ
00011 11110 011_ A=A-M
00011 00001 0110
Q[0]=0 And
restore A
300011 00010 110_ shift left AQ
00011 11111 110_ A=A-M
00011 00010 1100
Q[0]=0And
restore A
200011 00101 100_ shift left AQ
00011 00010 100_ A=A-M
00011 00010 1001 Q[0]=1
100011 00101 001_ shift left AQ
00011 00010 001_ A=A-M
00011 00010 (2)0011 (3) Q[0]=1
M = 00011
M’ = 11100
M’+1 = 11101
-M = 11101
-M = 11101

16. Division by Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
nM A Q Operation
400011 (3)00000 (0)1011 (11)initialize
00011 00001 011_ shift left AQ
00011 11110 011_ A=A-M
00011 00001 0110
Q[0]=0 And
restore A
300011 00010 110_ shift left AQ
00011 11111 110_ A=A-M
00011 00010 1100
Q[0]=0And
restore A
200011 00101 100_ shift left AQ
00011 00010 100_ A=A-M
00011 00010 1001 Q[0]=1
100011 00101 001_ shift left AQ
00011 00010 001_ A=A-M
00011 00010 (2)0011 (3) Q[0]=1

17. Division by Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
Start
nnoof bits
M Divisor
A 0
Q Dividend
Shift left AQ
A= A -M
MSB
of A
Q[0] = 1
Q[0] = 0
Restore A
n = n-1
Is n = 0
Quotient in Q
Remainder in A
Stop
=1=0
Yes
No
nM A Q Operation
400011 (3)00000 (0)1011 (11)initialize
00011 00001 011_ shift left AQ
00011 11110 011_ A=A-M
00011 00001 0110
Q[0]=0 And
restore A
300011 00010 110_ shift left AQ
00011 11111 110_ A=A-M
00011 00010 1100
Q[0]=0And
restore A
200011 00101 100_ shift left AQ
00011 00010 100_ A=A-M
00011 00010 1001 Q[0]=1
100011 00101 001_ shift left AQ
00011 00010 001_ A=A-M
00011 00010 (2)0011 (3) Q[0]=1
M = 00011
M’ = 11100
M’+1 = 11101
-M = 11101
-M = 11101

18. Division by Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
nM A Q Operation
400011 (3)00000 (0)1011 (11)initialize
00011 00001 011_ shift left AQ
00011 11110 011_ A=A-M
00011 00001 0110
Q[0]=0 And
restore A
300011 00010 110_ shift left AQ
00011 11111 110_ A=A-M
00011 00010 1100
Q[0]=0And
restore A
200011 00101 100_ shift left AQ
00011 00010 100_ A=A-M
00011 00010 1001 Q[0]=1
100011 00101 001_ shift left AQ
00011 00010 001_ A=A-M
00011 00010 (2)0011 (3) Q[0]=1

19. Division by Restore Method
11(Dividend)/3(Divisor)3(Quotient) and 2(Remainder)
Start
nnoof bits
M Divisor
A 0
Q Dividend
Shift left AQ
A= A -M
MSB
of A
Q[0] = 1
Q[0] = 0
Restore A
n = n-1
Is n = 0
Quotient in Q
Remainder in A
Stop
=1=0
Yes
No
nM A Q Operation
400011 (3)00000 (0)1011 (11)initialize
00011 00001 011_ shift left AQ
00011 11110 011_ A=A-M
00011 00001 0110
Q[0]=0 And
restore A
300011 00010 110_ shift left AQ
00011 11111 110_ A=A-M
00011 00010 1100
Q[0]=0And
restore A
200011 00101 100_ shift left AQ
00011 00010 100_ A=A-M
00011 00010 1001 Q[0]=1
100011 00101 001_ shift left AQ
00011 00010 001_ A=A-M
00011 00010 (2)0011 (3) Q[0]=1