Restoring & Non-Restoring Division Algorithm: Organization and Architecture
Division is one of the fundamental operations in computer architecture and plays a crucial role in various computational tasks.
There are several algorithms used for division, and two of the most commonly employed ones are the Restoring Division Algorithm and the Non-Restoring Division Algorithm.
Division in Computer Architecture
Before diving into the specifics of the Restoring and Non-Restoring Division Algorithms, let's briefly understand why division is essential in computer architecture.
Division is the process of finding the quotient and remainder when one number (the dividend) is divided by another (the divisor).
It is a fundamental arithmetic operation used in various applications, including numeric calculations, data processing, and control flow operations in programs.
Restoring Division Algorithm
The Restoring Division Algorithm is one of the earliest methods used for performing division in computer architecture. It operates on binary numbers and follows these basic steps:
Initialization: Initialize a set of registers to hold the dividend, divisor, quotient, and other temporary values.
Subtraction: Repeatedly subtract the divisor from the dividend until the dividend becomes smaller than the divisor. At each step, record a "1" in the quotient register.
Restoring Step: If the result of the subtraction in step 2 is negative (i.e., the dividend becomes negative), restore the dividend to its previous value by adding the divisor back.
Shift: Shift both the dividend and quotient registers to the left by one bit position.
Repeat: Repeat steps 2-4 until the quotient is complete.
Finalization: The quotient register now holds the quotient, and the dividend register holds the remainder.
Restoring Division Architecture
The architecture for Restoring Division typically consists of several key components:
Registers: These include registers for the dividend, divisor, quotient, and other temporary values.
ALU (Arithmetic Logic Unit): The ALU performs subtraction and addition operations during the algorithm's execution.
Control Unit: The control unit manages the sequencing of operations and controls the shifting and decision-making processes.
Clock: A clock signal synchronizes the operations in the algorithm.
Non-Restoring Division Algorithm
The Non-Restoring Division Algorithm is an alternative to the Restoring Division Algorithm and is more efficient in terms of hardware implementation. Like the Restoring Division Algorithm, it operates on binary numbers and involves the following steps:
Initialization: Initialize registers for the dividend, divisor, quotient, and other temporary values.
Guessing: Start by making an initial guess for the quotient. This guess is typically based on the most significant bits of the dividend and divisor.
Subtraction: Subtract the guessed quotient times the divisor from the dividend. If the result is negative, add the divisor back to the dividend.
Shift: Shift both the dividend and quotient registers to the left by one bit position.
Repeat: Repeat steps 3-4 until the quotient is complete.
Finalization: The quotient register holds the quotient, and the dividend register holds the remainder.
Non-Restoring Division Architecture
The architecture for Non-Restoring Division is somewhat similar to that of Restoring Division but with a few optimizations:
Registers: As with Restoring Division, registers are used for storing the dividend, divisor, quotient, and temporary values.
ALU: The ALU is used for subtraction and addition operations, similar to the Restoring Division Algorithm.
Control Unit: The control unit manages the sequencing of operations and controls the shifting and decision-making processes.
Clock: A clock signal is used to synchronize the operations in the algorithm.
Differences between Restoring and Non-Restoring Division
While both Restoring and Non-Restoring Division Algorithms achieve the same result (division of two binary numbers), they differ in several key aspects:
Restoration Step: Restoring Division has a restoration step where the dividend is restored if it becomes negative after subtraction. Non-Restoring Division avoids this step, making it more hardware-efficient.
Quotient Calculation: In Restoring Division, the quotient is calculated directly during subtraction. In Non-Restoring Division, an initial guess for the quotient is made, and adjustments are made during each iteration.
Hardware Efficiency: Non-Restoring Division is generally more hardware-efficient due to the absence of the restoration step. It requires fewer hardware resources to implement.
Speed: Non-Restoring Division is often faster than Restoring Division due to its reduced number of steps and simpler logic.
Restoring Division Algorithm for Unsigned Integer
A division algorithm provides a quotient and a remainder when we divide two numbers. They are generally of two types slow algorithm and fast algorithm.
Slow division algorithms are restoring, non-restoring, non-performing restoring, SRT algorithm, and under fast comes to Newton–Raphson, and Goldschmidt.
In this article, will be performing restoring algorithm for an unsigned integer. Restoring term is due to fact that the value of register A is restored after each iteration.
Here, register Q contains the quotient, and register A contains the remainder. Here, the n-bit dividend is loaded in Q, and the divisor is loaded in M.
Value of the Register is initially kept 0 and this is the register whose value is restored during iteration due to which it is named Restoring.
Let’s pick the step involved:
- Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
- Step-2: Then the content of register A and Q is shifted right as if they are a single unit
- Step-3: Then content of register M is subtracted from A and the result is stored in A
- Step-4: Then the most significant bit of the A is checked if it is 0 the least significant bit of Q is set to 1 otherwise if it is 1 the least significant bit of Q is set to 0 and value of register A is restored i.e the value of A before the subtraction with M
- Step-5: The value of counter n is decremented
- Step-6: If the value of n becomes zero we get of the loop otherwise we repeat fro step 2
- Step-7: Finally, the register Q contains the quotient and A contain remainder
Examples:
Perform Division Restoring Algorithm
Dividend = 11
Divisor = 3
|
n |
M |
A |
Q |
Operation |
|
4 |
00011 |
00000 |
1011 |
initialize |
|
00011 |
00001 |
011_ |
shift left AQ |
|
|
00011 |
11110 |
011_ |
A=A-M |
|
|
00011 |
00001 |
0110 |
Q[0]=0 And restore A |
|
|
3 |
00011 |
00010 |
110_ |
shift left AQ |
|
00011 |
11111 |
110_ |
A=A-M |
|
|
00011 |
00010 |
1100 |
Q[0]=0 |
|
|
2 |
00011 |
00101 |
100_ |
shift left AQ |
|
00011 |
00010 |
100_ |
A=A-M |
|
|
00011 |
00010 |
1001 |
Q[0]=1 |
|
|
1 |
00011 |
00101 |
001_ |
shift left AQ |
|
00011 |
00010 |
001_ |
A=A-M |
|
|
00011 |
00010 |
0011 |
Q[0]=1 |
Remember to restore the value of A most significant bit of A is 1. As that register Q contain the quotient, i.e. 3 and register A contain remainder 2.
Non-Restoring Division For Unsigned Integer
In an earlier post Restoring Division learned about restoring division. Now, here perform Non-
Restoring division, it is less complex than the restoring one because simpler operations is involved i.e. addition and subtraction, also now restoring step is performed.
In the method, rely on the sign bit of the register which initially contains zero named as A.
Here is the flow chart is given below.
Let’s pick the step involved:
- Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
- Step-2: Check the sign bit of register A
- Step-3: If it is 1 shift left content of AQ and perform A = A+M, otherwise shift left AQ and perform A = A-M (means add 2’s complement of M to A and store it to A)
- Step-4: Again the sign bit of register A
- Step-5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0] means least significant bit of register Q)
- Step-6: Decrements value of N by 1
- Step-7: If N is not equal to zero go to Step 2 otherwise go to next step
- Step-8: If sign bit of A is 1 then perform A = A+M
- Step-9: Register Q contain quotient and A contain remainder
Examples: Perform Non_Restoring Division for Unsigned Integer
Dividend =11
Divisor =3
-M =11101
|
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 |
Quotient = 3 (Q)
Remainder = 2 (A)