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 method981*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.