Restoring Division Algorithm for Signed Numbers
Previous algorithms used for division are Restoring and Non restoration algorithms for Unsigned Numbers.Those are for unsigned numbers.Now we will look into the algorithm for division of signed numbers. Similarly here also the article would explain in detail about restoring division algorithm.
Restoring division algorithm Flowchart
Restoring division algorithm for signed numbers:
1)Number of steps is equal to the number of bits in the dividend.
2)At each step perform a left shift.
3)If A(Accumulator) and m(Divisor) are the same sign,then subtract m else add m.
4)If sign of A changes,then unsuccessful, make Q bit 0 and restore.
5)If the sign of A remains the same or dividend becomes 0 then successful.
6)For successful step ,make Q bit 1,do not restore.
Note:
- Quotient given by this algorithm is always a positive number.
- Remainder is same sign as the dividend
Restoring division for signed Numbers
Ex: 7/(-3)
7 = 0 1 1 1 -7 = 1 0 0 1
3 = 0 0 1 1 -3 = 1 1 0 1
Step 1:
Accumulator Dividend Divisor
| A | Q(7) | m(-3) | |
| 0 0 0 0 | 0 1 1 1 | 1 1 0 1 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 0 0 0 0 +1 1 0 1 1 1 0 1 0 0 0 0 | 1 1 1 _ 1 1 1 0 |
Step 2:
| Left shift Add m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 1 0 0 0 0 1 | 1 1 0 _ 1 1 0 0 |
Step 3:
| Left shift Add m successful | 0 0 1 1 +1 1 0 1 0 0 0 0 | 1 0 0 _ 1 0 0 1 |
Step 4:
| Left shift Add m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 1 0 0 0 0 1 | 0 0 1 _ 0 0 1 0 | |
| Remainder(1) | Quotient(2) |
Restoration Table:
| A | Q(7) | m(-3) | |
| 0 0 0 0 | 0 1 1 1 | 1 1 0 1 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 0 0 0 0 +1 1 0 1 1 1 0 1 0 0 0 0 | 1 1 1 _ 1 1 1 0 | |
| Left shift Add m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 1 0 0 0 0 1 | 1 1 0 _ 1 1 0 0 | |
| Left shift Add m successful | 0 0 1 1 +1 1 0 1 0 0 0 0 | 1 0 0 _ 1 0 0 1 | |
| Left shift Add m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 1 0 0 0 0 1 | 0 0 1 _ 0 0 1 0 | |
| Remainder(1) | Quotient(2) |
Ex:( -7) / (3)
7 = 0 1 1 1 -7 = 1 0 0 1
3 = 0 0 1 1 -3 = 1 1 0 1
Since the dividend is negative accumulator is assumed to be 1 1 1 1.
Step 1:
Accumulator Dividend Divisor
| A | Q(-7) | m(3) | |
| 1 1 1 1 | 1 0 0 1 | 1 1 0 1 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 1 1 1 1 +0 0 1 1 0 0 1 0 1 1 1 1 | 0 0 1 _ 0 0 1 0 |
Step 2:
| Left shift Add m unsuccessful Restoration | 1 1 1 0 +0 0 1 1 0 0 0 1 1 1 1 0 | 0 1 0 _ 0 1 0 0 |
Step 3:
| Left shift Add m successful | 1 1 0 0 +0 0 1 1 1 1 1 1 | 1 0 0 _ 1 0 0 1 |
Step 4:
| Left shift Add m unsuccessful Restoration | 1 1 1 1 +0 0 1 1 0 0 1 0 1 1 1 1 | 0 0 1 _ 0 0 1 0 | |
| Remainder(-1) | Quotient(2) |
Restoration Table:
| A | Q(-7) | m(3) | |
| 1 1 1 1 | 1 0 0 1 | 1 1 0 1 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 1 1 1 1 +0 0 1 1 0 0 1 0 1 1 1 1 | 0 0 1 _ 0 0 1 0 | |
| Left shift Add m unsuccessful Restoration | 1 1 1 0 +0 0 1 1 0 0 0 1 1 1 1 0 | 0 1 0 _ 0 1 0 0 | |
| Left shift Add m successful | 1 1 0 0 +0 0 1 1 1 1 1 1 | 1 0 0 _ 1 0 0 1 | |
| Left shift Add m unsuccessful Restoration | 1 1 1 1 +0 0 1 1 0 0 1 0 1 1 1 1 | 0 0 1 _ 0 0 1 0 | |
| Remainder(-1) | Quotient(2) |
We can extend this understand and solve for bigger numbers as well.
Ex:( 14) / (-2)
14 = 0 1 1 1 0 -14 = 1 0 0 1 0
2 = 0 0 0 1 0 -2 = 1 1 1 1 0
Since the number of dividend bits are 5,number of steps are 5.
Step 1:
Accumulator Dividend Divisor
| A | Q(14) | m(-2) | |
| 0 0 0 0 0 | 0 1 1 1 0 | 1 1 1 1 0 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 0 0 0 0 0 +1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 | 1 1 1 0 _ 1 1 1 0 0 |
Step 2:
| Left shift Add m unsuccessful Restoration | 0 0 0 0 1 +1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 | 1 1 0 0 _ 1 1 0 0 0 |
Step 3:
| Left shift Add m successful | 0 0 0 1 1 +1 1 1 1 0 0 0 0 0 1 | 1 0 0 0 _ 1 0 0 0 1 |
Step 4:
| Left shift Add m successful | 0 0 0 1 1 +1 1 1 1 0 0 0 0 0 1 | 0 0 0 1 _ 0 0 0 1 1 |
Step 5:
| Left shift Add m successful | 0 0 0 1 0 +1 1 1 1 0 0 0 0 0 0 | 0 0 1 1 _ 0 0 1 1 1 | |
| Remainder(0) | Quotient(7) |
Restoration Table for restoring division algorithm:
| A | Q(14) | m(-2) | |
| 0 0 0 0 0 | 0 1 1 1 0 | 1 1 1 1 0 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 0 0 0 0 0 +1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 | 1 1 1 0 _ 1 1 1 0 0 | |
| Left shift Add m unsuccessful Restoration | 0 0 0 0 1 +1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 | 1 1 0 0 _ 1 1 0 0 0 | |
| Left shift Add m successful | 0 0 0 1 1 +1 1 1 1 0 0 0 0 0 1 | 1 0 0 0 _ 1 0 0 0 1 | |
| Left shift Add m successful | 0 0 0 1 1 +1 1 1 1 0 0 0 0 0 1 | 0 0 0 1 _ 0 0 0 1 1 | |
| Left shift Add m successful | 0 0 0 1 0 +1 1 1 1 0 0 0 0 0 0 | 0 0 1 1 _ 0 0 1 1 1 | |
| Remainder(0) | Quotient(7) |
Ex:( -14) / (2)
14 = 0 1 1 1 0 -14 = 1 0 0 1 0
2 = 0 0 0 1 0 -2 = 1 1 1 1 0
Since the number of dividend bits are 5,number of steps are 5.
Step 1:
Accumulator Dividend Divisor
| A | Q(-14) | m(2) | |
| 1 1 1 1 1 | 1 0 0 1 0 | 0 0 0 1 0 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 1 1 1 1 1 +0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 | 0 0 1 0 _ 0 0 1 0 0 |
Step 2:
| Left shift Add m unsuccessful Restoration | 1 1 1 1 0 +0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 | 0 1 0 0 _ 0 1 0 0 0 |
Step 3:
| Left shift Add m successful | 1 1 1 0 0 +0 0 0 1 0 1 1 1 1 0 | 1 0 0 0 _ 1 0 0 0 1 |
Step 4:
| Left shift Add m successful | 1 1 1 0 1 +0 0 0 1 0 1 1 1 1 1 | 0 0 0 1 _ 0 0 0 1 1 |
Step 5:
| Left shift Add m successful | 1 1 1 1 0 +0 0 0 1 0 0 0 0 0 0 | 0 0 1 1 _ 0 0 1 1 1 | |
| Remainder(0) | Quotient(7) |
Restoration Table:
| A | Q(-14) | m(2) | |
| 1 1 1 1 1 | 1 0 0 1 0 | 0 0 0 1 0 | |
| Left shift Add m MSB:1=-veMSB:0=+veSign change Unsuccessful Restoration | 1 1 1 1 1 +0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 | 0 0 1 0 _ 0 0 1 0 0 | |
| Left shift Add m unsuccessful Restoration | 1 1 1 1 0 +0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 | 0 1 0 0 _ 0 1 0 0 0 | |
| Left shift Add m successful | 1 1 1 0 0 +0 0 0 1 0 1 1 1 1 0 | 1 0 0 0 _ 1 0 0 0 1 | |
| Left shift Add m successful | 1 1 1 0 1 +0 0 0 1 0 1 1 1 1 1 | 0 0 0 1 _ 0 0 0 1 1 | |
| Left shift Add m | 1 1 1 1 0 +0 0 0 1 0 0 0 0 0 0 | 0 0 1 1 _ 0 0 1 1 1 | |
| Remainder(0) | Quotient(7) |