Restoring Division Algorithm for Unsigned Numbers
Division can be performed by repeated subtraction.But repeated subtractions are slow. We have to subtract the divisor from divident until zero comes, and number of subractions gives us the quotient. So there are two main methods and they are restoring division algorithm and Non restoring division algorithm. These two methods are used for Unsigned divisions. Algorithms for Signed Numbers
ex:1000/1 means we need to subtract 1 for 1000 times from 1000.It takes 1000 steps to accomplish one division operation.
Hence we opt for fast methods like
- Restoring Division Algorithm
- Non Restoring Division Algorithm
Restoring Division Algorithm FlowChart
1)The number of steps is equal to the number of bits in the dividend.
2)At each step left shift the dividend,make an attempt to subtract the divisor.
3)If the result is positive the step is successfull.
4)The quotient bit is 1,no restoration is required.
5)If the result is negative the step is unsuccessful.
6)The quotient bit is 0, restoration is performed by adding the divisor.
Ex: 7 / 3 ,7 divided by 3
3 = 0 0 1 1 – 3 = 1 1 0 1
7 = 0 1 1 1 -7 = 1 0 0 1
Step 1:
Accumulator Dividend Divisor
| A | Q(7) | m(3) | |
| 0 0 0 0 | 0 1 1 1 | 0 0 1 1 | |
| Left shift Sub m MSB:1=-veMSB:0=+ve 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 Sub m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 0 1 0 0 0 1 | 1 1 0 _ 1 1 0 0 |
Step 3:
| Left shift Sub 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 Sub 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 | 0 0 1 1 | |
| Left shift Sub m MSB:1=-veMSB:0=+ve 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 Sub m unsuccessful Restoration | 0 0 0 1 +1 1 0 1 1 1 0 1 0 0 0 1 | 1 1 0 _ 1 1 0 0 | |
| Left shift Sub m successful | 0 0 1 1 +1 1 0 1 0 0 0 0 | 1 0 0 _ 1 0 0 1 | |
| Left shift Sub 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) |
Non Restoring Division Algorithm FlowChart
Restoration step takes up additional time,hence to overcome the drawback of restoration algorithm we use a non restorating division algorithm.
1)The number of steps is equal to the number of bits in the dividend.
2)At each step left shift the dividend,make an attempt to subtract the divisor.
3)If the result is positive the step is successfull.
4)The quotient bit is 1,no restoration is required.
5)If the result is negative the step is unsuccessful.
6)The quotient bit is 0,no restoration is performed.
7) In the next step, perform addition of the divisor.
Note:If the last step is unsuccessful, restoration is performed.
Ex: 7 / 3 ,7 divided by 3
3 = 0 0 1 1 – 3 = 1 1 0 1
7 = 0 1 1 1 -7 = 1 0 0 1
Step 1:
Accumulator Dividend Divisor
| A | Q(7) | m(3) | |
| 0 0 0 0 | 0 1 1 1 | 0 0 1 1 | |
| Left shift Sub m MSB:1=-veMSB:0=+ve Next Add | 0 0 0 0 +1 1 0 1 1 1 0 1 | 1 1 1 _ 1 1 1 0 |
Step 2:
| Left shift add m unsuccessful Next add | 1 0 1 1 +0 0 1 1 1 1 1 0 | 1 1 0 _ 1 1 0 0 |
Step 3:
| Left shift Add m successful Next sub | 1 1 0 1 +0 0 1 1 0 0 0 0 | 1 0 0 _ 1 0 0 1 |
Step 4:
| Left shift Sub 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) |
Non Restoration Table:
| A | Q(7) | m(3) | |
| 0 0 0 0 | 0 1 1 1 | 0 0 1 1 | |
| Left shift Sub m MSB:1=-veMSB:0=+ve Next Add | 0 0 0 0 +1 1 0 1 1 1 0 1 | 1 1 1 _ 1 1 1 0 | |
| Left shift add m unsuccessful Next add | 1 0 1 1 +0 0 1 1 1 1 1 0 | 1 1 0 _ 1 1 0 0 | |
| Left shift Add m successful Next sub | 1 1 0 1 +0 0 1 1 0 0 0 0 | 1 0 0 _ 1 0 0 1 | |
| Left shift Sub 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) |
Thus, remainder 1 and quotient 2 is obtained for 7 divided by 3.