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.2 years ago  • written 2.2 years ago by gravatar for Barkha Barkha750
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.

enter image description here

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.

enter image description here

Let us formulate this method-

enter image description here

The 2 digit numbers are

enter image description here

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

enter image description here

We can generalize this formula as-

enter image description here

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

ADD COMMENTlink
written 2.2 years ago by gravatar for Barkha Barkha750
Please log in to add an answer.