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

ADD COMMENTlink
 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.

ADD COMMENTlink
 written 2.5 years ago by Barkha • 750
Please log in to add an answer.