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
If a is odd store b
A=a/2 and b=b*2
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
Write the algorithm to find the product of two numbers for all the methods explained.
Hand simulate the algorithm for atleast 10 different numbers.
Implement the same for verification.
Write a program to find the maximum and minimum of the list of n element with and without using recursion.
