Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Multiplication Algorithm
2.1.
Hardware Implementation for Signed-Magnitude Data
2.2.
Hardware Algorithm
3.
Division Algorithm
3.1.
Hardware Implementation for Signed-Magnitude Data
3.2.
Divide Overflow
3.3.
Hardware-algorithm
4.
FAQs
5.
Key Takeaways 
Last Updated: Mar 27, 2024
Easy

Multiplication and Division

Author Apoorv Dixit
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Arithmetic instructions in digital computers work on data to produce the results necessary for solving computational problems. These instructions are responsible for processing data on a computer. There are four basic arithmetic operations, addition, subtraction, multiplication, and division. 

This article will discuss multiplication and division arithmetic algorithms and show the procedure for digital hardware implementation.

Recommended Topic, Microinstruction in Computer Architecture and Difference Between Jfet and Mosfet

Multiplication Algorithm

Multiplication of fixed-point binary numbers in signed-magnitude representation is done by successive shift and add operations. For example, multiplication of numbers 10111(23) and 10011(19).

23        10111

19      x 10011


             10111

           10111x

         00000xx      +(adding all)

       00000xxx


      110110101     Product 437

The process consists of looking at successive Multiplier, least significant bit first. If the Multiplier is 1, the multiplicand is copied down; otherwise, zero is copied. And like we do in standard multiplication, the numbers copied down in successive lines are shifted one position to the left. Finally, all binaries are added, and the total sum is the result. The sign of the product(result) is determined from the signs of multiplicand and Multiplier. If they are alike, the final product sign is positive. If they are unlike, the sign of the product is negative. 

Recommended Topic - Shift Registers in Digital Electronics and what is middleware

Hardware Implementation for Signed-Magnitude Data

Multiplication is implemented in digital computers by changing the process slightly. First, instead of providing registers to store bits and binary numbers simultaneously, it is better to give an adder for the sum of only two binary numbers and then successively accumulate the partial product. In the second step, instead of shifting the multiplicand to the left, shift the partial product to the right. In the third step, the corresponding bit of the Multiplier is zero(0); there is no need to add zeros to the partial product since it will not change the value.

The hardware multiplication consists of registers and the equipment shown above. The Multiplier is stored in the register Q and its sign is Qs. Registers Q and B are used to store multiplicand and Multiplier, respectively, and register A store's partial products during multiplication.

The sequence counter(SC) at the beginning is set to a number equal to the number of bits in the Multiplier, and the counter is decremented by one after forming each partial product. The product begins when the counter reaches zero, and the process stops.

Three flip flops are required to store the sign bit of registers (sign A, sign B, and sign Q).

Flip flop E-stores carry bits generated during partial product addition.

This hardware unit Complement and Parallel adder calculate a partial product, i.e., perform addition required.

Hardware Algorithm

The diagram below shows the flowchart of the hardware multiply algorithm. At the start, the multiplicand is in B, and the Multiplier is Q. Their corresponding signs are in Bs and Qs. 

                 

  • We compare the signs of registers B(Bs) and Q(Qs) using the functionality of XOR and output stored in As (the sign of A register). 

Note: Initially, register A  and E flip flops have a value 0. The sequence counter is initialized with the value n, n is the number of bits in the Multiplier.

  • Now we check the least significant bit of Multiplier. Add the multiplicand (register B) with the content of register A if it is 1. The result is assigned in A register with a carry bit in flip flop E. Content of E A Q is shifted to the right by one position, i.e., the content of E is shifted to most significant bit (MSB) of A, and least significant bit of A is shifted to the most significant bit of Q.
  • If Qn = 0, only shift right operation on the content of E A Q is performed similarly.
  • Content of Sequence counter is decremented by 1.
  • Check the content of the Sequence counter (SC) content; if it is 0, end the process, and the final product is present in registers A and Q, or repeat the process.

Time for an Example:

We have to multiply two numbers B and Q, B=10111, Q=10011 ( the signed bits of these numbers will be handled separately, for that you can find xor of B and Q and the result will be stored in signed bits of A and Q).

Initially, A and E are accumulators initialized to 0. SC is a sequence counter which is initially equal to the number of bits in multiplier or multiplicand( here 5)

E

A

Q

SC

0

00000

10011

5

Since the value of Qn(last bit) is 1, A will be added to B 00000 + 10111 = 10111 and then shift right will be performed. (It's just a simple right shift operation in which the last bit of Q will be lost and all other bits shifted rightwards).

E

A

Q

SC

0

01011

11001

4

Again the value of Qn is 1, B will be added to A( 10111+ 01011= 00010 and E=1), then shift right will be performed. The bit 1 in E will be right-shifted to A

E

A

Q

SC

0

10001

01100

3

Now the value of Qn is 0 therefore only a shift right has to be performed without adding B

E

A

Q

SC

0

01000

10110

2

Again Qn=0, the shift right has to be performed. 

E

A

Q

SC

0

00100

01011

1

Now, Qn =1, adding B to A then right shift.

E

A

Q

SC

0

01101

10101

0

The sequence counter has reached 0, therefore no further computation needs to be performed. The values of A and Q store the final result.

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

Division Algorithm

Division to two fixed-point binary numbers in signed-magnitude representation is done by the process of successive compare, shift, and subtract operations. The binary division is simpler than decimal because the quotient is either 0 or 1. There is no need to calculate how many times the dividend or partial remainder fires into the divisor. You can follow the following steps for binary division.

Step 1: Compare the divisor with the dividend; if the divisor is greater, place 0 as the quotient, then bring down the second bit of the dividend. If the divisor is smaller, multiply it by one, and the result must be subtracted. Then, subtract the result from the above to get the remainder.

Step 2: Bring down the next number bit from the dividend and perform step1.

Step 3: Repeat the whole process until the remainder becomes 0, or the whole dividend is divided.


Source: cuemath.com

Hardware Implementation for Signed-Magnitude Data

When the division is implemented in a digital system, it is easy to alter the process little. Instead of shifting the divisor to the right, the partial remainder or dividend is shifted left, thus leaving the two numbers in the required relative position. After that, subtraction can be achieved by adding A to the 2's complement of B. The hardware implementation for division is identical to multiplication and consists of the same components as shown above in the multiplication hardware implementation. 

Divide Overflow

The division operation sometimes results in a quotient with an overflow. It is not a problem when working with pen and paper, but it is critical to implement the operation with hardware. This is because the register's length is finite and will not hold a number that exceeds the standard length. 

Hardware-algorithm

The hardware algorithm for division is shown in the flowchart below.

                 

In the above flow chart:

  • The A and Q contain the dividend, and B contains the divisor. The result sign is transferred into Qs to be part of the quotient. SC is the sequence counter specifying the number of bits in the quotient.
  • Since we have to save an operand with its sign, the sign inhabits the one bit of the word, and the size of magnitude will be n -1 bits.
  • The condition of divide-overflow is checked by subtracting the divisor in B from the half of bits of the dividend stored in A. If A ≥ B.
  • The division of the magnitudes starts by shl dividend in AQ to the left in the high-order bit shifted into E. 
  • In this case, B must be subtracted from EA, and one should insert into Q for the quotient bit.
  • If the shift-left operation (shl) inserts a 0 into E, the divisor is subtracted by adding its 2's complement value, and the carry is moved into E. If E = 1, it means A ≥ B; thus, Q is set to 1. If E = 0, A < B and the original number is reimposed by adding B into A.
  • Now, this process is repeated with register A containing the partial remainder.

FAQs

  1. What is computer arithmetic?
    Computer arithmetic is a field of computer science that works on how computers should represent numbers and perform operations on them.
     
  2. What are types of arithmetic operations?
    There are four elementary operations in arithmetic: addition, subtraction, multiplication, and division.
     
  3. What is a multiplier in multiplication?
    In the vertical column multiplication method, the Multiplier is the number on top. The Multiplier amplifies the base value of something else. For example, in the multiplication statement 6 × 2 = 12, the multiplier 6 amplifies the value of 2 to 12.
     
  4. What is divided in the division?
    What is being divided is the dividend. The dividend is divided by the divisor, and that gives the quotient as a result. For example, 24/5, 24 is the dividend, 5 is the divisor, and 4 is the quotient.
     
  5. What is an algorithm?
    An algorithm can be defined as a set of instructions for solving a problem or accomplishing a task. One example of an algorithm is a tea guide, which consists of specific instructions for making a tea.

Key Takeaways 

In this article, we discussed multiplication and division arithmetic operations and their hardware implementations and flowcharts of algorithms. You can refer to Register in Computer and Repeater in Computer Network to learn more about computer architecture.

Recommended Reading:  Data Warehouse Architecture

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; take a look at the interview experiences and interview bundle for placement preparations.Do upvote our blog to help other ninjas grow.

Happy Learning!

Previous article
Addition and Subtraction
Next article
Bus and Memory Transfer
Live masterclass