Explain the concept of multiplying long integers using divide and conquer

327views

written 8.9 years ago by

teamques10 ★ 70k

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 COMMENT EDIT