Integer multipliation
Printed From: One Stop GATE
Category: GATE Technical Discussions
Forum Name: GATE CS
Forum Discription: General Technical Discussions, Queries, doubts etc. for GATE in CS.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=1095
Printed Date: 23Feb2025 at 11:46am
Topic: Integer multipliation
Posted By: gita
Subject: Integer multipliation
Date Posted: 08Apr2007 at 10:45pm
4.3 Integer multiplication
There are various methods of obtaining the product of two numbers. The
repeated addition method is left as an assignment for the reader. The
reader is expected to find the product of some bigger numbers using the
repeated addition method.
Another way of finding the product is the one we generally use i.e., the left shift method.
4.3.1 left shift method
981*1234
3924
2943*
1962**
981***
1210554
In this method, a=981 is the multiplicand and b=1234 is the multiplier.
A is multiplied by every digit of b starting from right to left. On
each multiplication the subsequent products are shifted one place left.
Finally the products obtained by multiplying a by each digit of b is
summed up to obtain the final product.
The above product can also be obtained by a right shift method, which can be illustrated as follows,
4.3.2 right shift method
981*1234
981
1962
*2943
**3924
1210554
In the above method, a is multiplied by each digit of b from leftmost
digit to rightmost digit. On every multiplication the product is
shifted one place to the right and finally all the products obtained by
multiplying ‘a’ by each digit of ‘b’ is added to obtain the final
result.
The product of two numbers can also be obtained by dividing ‘a’ and multiplying ‘b’ by 2 repeatedly until a<=1.
4.3.3 halving and doubling method
Let a=981 and b=1234
The steps to be followed are
1. If a is odd store b
2. A=a/2 and b=b*2
3. Repeat step 2 and step 1 till a<=1
a b result
981 1234 1234
490 2468 ------------
245 4936 4936
122 9872 ---------
61 19744 19744
30 39488 ------------
15 78976 78976
7 157952 157952
3 315904 315904
1 631808 631808
Sum=1210554
The above method is called the halving and doubling method.
4.3.4 Speed up algorithm:
In this method we split the number till it is easier to multiply. i.e.,
we split 0981 into 09 and 81 and 1234 into 12 and 34. 09 is then
multiplied by both 12 and 34 but, the products are shifted ‘n’ places
left before adding. The number of shifts ‘n’ is decided as follows
Multiplication sequence shifts
09*12 4 108****
09*34 2 306**
81*12 2 972**
81*34 0 2754
Sum=1210554
For 0981*1234, multiplication of 34 and 81 takes zero shifts, 34*09 takes 2 shifts, 12 and 81 takes 2 shifts and so on.
Exercise 4
1. Write the algorithm to find the product of two numbers for all the methods explained.
2. Hand simulate the algorithm for atleast 10 different numbers.
3. Implement the same for verification.
4. Write a program to find the maximum and minimum of the list of n element with and without using recursion.
click here for more details:
http://%20%20%20www.vyomworld.com/gate/cs/ada/4.3.asp - http://www.vyomworld.com/gate/cs/ada/4.3.asp
|
|