Restoring & NonRestoring 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 NonRestoring Division Algorithm.
Division in Computer Architecture
Before diving into the specifics of the Restoring and NonRestoring 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 24 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 decisionmaking processes.
Clock: A clock signal synchronizes the operations in the algorithm.
NonRestoring Division Algorithm
The NonRestoring 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 34 until the quotient is complete.
Finalization: The quotient register holds the quotient, and the dividend register holds the remainder.
NonRestoring Division Architecture
The architecture for NonRestoring 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 decisionmaking processes.
Clock: A clock signal is used to synchronize the operations in the algorithm.
Differences between Restoring and NonRestoring Division
While both Restoring and NonRestoring 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. NonRestoring Division avoids this step, making it more hardwareefficient.
Quotient Calculation: In Restoring Division, the quotient is calculated directly during subtraction. In NonRestoring Division, an initial guess for the quotient is made, and adjustments are made during each iteration.
Hardware Efficiency: NonRestoring Division is generally more hardwareefficient due to the absence of the restoration step. It requires fewer hardware resources to implement.
Speed: NonRestoring 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, nonrestoring, nonperforming 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 nbit 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:
 Step1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
 Step2: Then the content of register A and Q is shifted right as if they are a single unit
 Step3: Then content of register M is subtracted from A and the result is stored in A
 Step4: 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
 Step5: The value of counter n is decremented
 Step6: If the value of n becomes zero we get of the loop otherwise we repeat fro step 2
 Step7: 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=AM 

00011 
00001 
0110 
Q[0]=0 And restore A 

3 
00011 
00010 
110_ 
shift left AQ 
00011 
11111 
110_ 
A=AM 

00011 
00010 
1100 
Q[0]=0 

2 
00011 
00101 
100_ 
shift left AQ 
00011 
00010 
100_ 
A=AM 

00011 
00010 
1001 
Q[0]=1 

1 
00011 
00101 
001_ 
shift left AQ 
00011 
00010 
001_ 
A=AM 

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.
NonRestoring 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:
 Step1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
 Step2: Check the sign bit of register A
 Step3: If it is 1 shift left content of AQ and perform A = A+M, otherwise shift left AQ and perform A = AM (means add 2’s complement of M to A and store it to A)
 Step4: Again the sign bit of register A
 Step5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0] means least significant bit of register Q)
 Step6: Decrements value of N by 1
 Step7: If N is not equal to zero go to Step 2 otherwise go to next step
 Step8: If sign bit of A is 1 then perform A = A+M
 Step9: 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=AM 

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=AM 

0 
00010 
0011 
Q[0]=1 
Quotient = 3 (Q)
Remainder = 2 (A)