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://www.vyomworld.com/gate/cs/ada/4.3.asp