Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the division restoring algorithm?
3.
Types of Division Algorithms
3.1.
Slow algorithm
3.2.
Fast algorithm
4.
Restoring Algorithm For Unsigned Integer
5.
Restoring Algorithm For Signed Integer
6.
Frequently Asked Questions
6.1.
What is division restoring algorithm in computer architecture?
6.2.
How do you perform restoring division?
6.3.
What is restoring or non-restoring division algorithm?
6.4.
What are the advantages of non-restoring division?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Introduction to Division Algorithm in Computer Architecture

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We all know what division is. It is a mathematical operation that gives a quotient and a remainder. We will see the hardware implementation of the Division algorithm in computer architecture. We use registers and counters while performing division. 

Let’s start with seeing the types of division algorithm in computer architecture.

What is the division restoring algorithm?

The restoring division algorithm is a method used for binary division in computer architecture. It involves repeatedly subtracting the divisor from the dividend and restoring the partial remainder if the result is negative. The algorithm uses a sign bit to track the sign of the partial remainder and adjusts accordingly. The process continues until the division is complete, and the quotient and remainder are obtained.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Types of Division Algorithms

Division algorithm in computer architecture is of two categories. 

The first one is Slow Division. In the slow division, we get one digit of the quotient every iteration. The algorithms for slow division category are Restoring, Non-Performing Restoring, Non-Restoring, and SRT. 

The second category is the Fast Division. In this method, the quotient is predicted to the closest approximation to the actual quotient, and then the calculation starts. The algorithms for fast division category are Newton–Raphson, and Goldschmidt.

Here we will discuss the restoring division algorithm in computer architecture for unsigned and signed integers.

Slow algorithm

It refers to a division algorithm that is relatively inefficient in terms of execution speed or computational complexity. It typically associated with traditional or elementary methods of long division, which may involve more steps and computations. It may have higher time complexity, making it less suitable for situations where speed is a critical factor.

Fast algorithm

It describes a division algorithm that is designed for efficient and quick computation, particularly in a digital or computer environment. It often involves optimization techniques to reduce the number of steps or operations required for division. Examples include algorithms tailored for specific hardware architectures or advanced mathematical methods that exploit patterns in binary or other representations.

Also see, MVVM Architecture Android

Restoring Algorithm For Unsigned Integer

The restoring division algorithm is a slow division algorithm that calculates the quotient digit by digit. This algorithm will generate a quotient and a remainder after the division algorithm. Division algorithm in computer architecture uses registers for storing the numbers and calculations. The division works with the assumption that the dividend is greater than the divisor. 

Restoring Algorithm For Unsigned Integer

This division algorithm in computer architecture uses three registers. Register A is initialized to 0register Q stores the dividend, and register M stores the divisoris used as a counter and stores the number of bits present in the dividend.

Let us see the flowchart for the restoring division algorithm in computer architecture.

flowchart for the restoring division algorithm

Let us understand the flowchart:

 

  1. We initialize the variables. Register A is initialized with 0, register Q will have the dividend, and register M will contain the divisor. is the counter and has a value equal to the number of bits present in the dividend.
     
  2. The value of AQ(here in this step, A and Q will be treated as a single unit) will shift to the left.                                                                   
  3. In this step, subtraction occurs. M will be subtracted from A, and A will store the result.
     
  4. In this step, we check for the most significant bit of A. Suppose the most significant bit in A is 1 after the above three stages in the restoring division algorithm in computer architecture. In that case, it will set the least significant bit of Q as 0, and the value of A will again become what it was before the subtraction operation in step 3. If the most significant bit in A is 0, then it will set the least significant bit of Q as 1.                                                                                                                                                                                                                 
  5. N is decreased by 1 in this step.                                                                                                                                                                          
  6. In this step, we check the value of N. If the value of N becomes 0, we break the loop here or move back to step 2.                                               
  7. In this step, we have our answer with the quotient in Q and the remainder in A.

 

Let us see an example of the restoring division algorithm in computer architecture:

Let the dividend be 0111(7) and the divisor 0011(3).

N M A Q Operation
4 0011 0000 0111 Initialization
    0000 111_ SHL AQ
    1101 111_ A= A-M
    0000 1110 Q[0]=0 and restore A
3 0011 0001 1100 SHL AQ
  0011 1110 110_ A=A-M
  0011 0001 1100 Q[0]=0 and restore A
2 0011 0011 100_ SHL AQ
  0011 0000 100_ A=A-M
  0011 0000 1001 Q[0]=1
1 0011 0001 001_ SHL AQ
  0011 1110 001_ A=A-M
  0011 0001 0010 Q[0]= 0 and restore A

We got the quotient as 0010, which is 2, and the remainder as 0001, which is 1.

Restoring Algorithm For Signed Integer

The restoring division algorithm in computer architecture is almost identical for both signed and unsigned integers. For signed integers, we only take the bits representing the magnitude of both the numbers, and at the end, we put the sign with the quotient. Everything else remains the same.

Read about Instruction Format in Computer Architecture

Frequently Asked Questions

What is division restoring algorithm in computer architecture?

Restoring algorithm is a binary division method in computer architecture. It restores partial remainders during the division process and uses a sign bit for tracking.

How do you perform restoring division?

To perform restoring division, use the restoring algorithm. Divide the binary numbers, restoring partial remainders and making adjustments based on the sign bit.

What is restoring or non-restoring division algorithm?

Restoring division involves restoring partial remainders during the process. Non-restoring division adjusts without restoring partial remainders, simplifying the algorithm and reducing hardware complexity.

What are the advantages of non-restoring division?

Non-restoring division has advantages such as simplicity and reduced hardware complexity compared to restoring division. This makes it an attractive choice in certain computing environments.

Conclusion

In this article, we learned about the division algorithm in computer architecture which is the Restoring Algorithm. We have discussed several types of division algorithm. We have also explained slow and fast algorithm. 

You can read about computer architecture concepts on Coding Ninjas Studio. Also, if you need help with any other subject, Coding Ninjas Studio has got you. Learn DBMSOSDSA, and Computer Networks in one place. 

Also Read - Repeater in Computer Network, Register in Computer , Design and Analysis of Algorithms, What Is a Motherboard

You can also read about the interview experiences of different candidates here

Happy learning!

Previous article
What is Booth's Algorithm in Computer Architecture?
Next article
Difference Between SRAM and DRAM
Live masterclass