Question: Explain the concept of multiplying long integers using divide and conquer
0

Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10M

Year: May 2016

 modified 2.5 years ago  • written 2.5 years ago by Barkha • 750
1

In this method multiply the multiplicand by each digit of multiplier and then add up all the properly shifted result. This method is also called grade-school multiplication.

But this method is not convenient for performing multiplication of large integers. Hence let us discuss an interesting algorithm of multiplying large integers. For example: consider multiplication of two integers 42 and 34. First let us represent these numbers according to positions.

Let us formulate this method-

The 2 digit numbers are

Let perform multiplication operation with the help of formula given in equation 1.

We can generalize this formula as-

Clearly, this algorithm can be implemented using recursion. This recursion can be stopped when n reaches to 0.