Design an algorithm to multiply large numbers

A multiplication algorithm is an algorithm (or method) to multiply two (or three) numbers. Depending on the size of the numbers, different algorithms are in use. Multiplication algorithms efficiently have existed since the advent of the decimal system. If a positional numeral system is used, a usual way of multiplying numbers is taught in schools as long multiplication, sometimes it is generally called grade-school multiplication, sometimes called Standard Algorithm: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results. It requires one to memorization of the multiplication table for single digits.
 

This is the usual algorithm for multiplying larger numbers by hand in base 10. Computers usually use a very similar shift and add algorithm in base 2. One doing long multiplication on paper will write down all the products and then add them together; an abacus-user will sum the products as soon as each one is computed. The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to n^2, or Theta(n^2)! in the big-O notation. Andrey Kolmogorov in 1952 conjectured that the classical algorithm was asymptotically optimal, it mean that any algorithm for that task would require Omega(n^2)! elementary operations.

Multiplication of large Integers :
 
Some applications, notably modern cryptology is require manipulation of integers that are over too decimal digits long. Since such integers are too long to fit in a single word of a modern computer, they require special treatment. This practical need supports investigations of algorithms for efficient manipulation of large integers. In this section, we outline an interesting algorithm for multiplying such numbers. Obviously, if we use the classic pen-and-pencil algorithm for multiplying two n-digit integers, each of the n digits of the first number is multiplied by each of the n digits of the second number for the total of n2 digit multiplications. (If one of the numbers has fewer digits than the other, we can pad a shorter number with leading zeros to equal their lengths.) Though it might appear that it would be impossible to design an algorithm with fewer than n2 digit multiplications, it turns out not to be the case.
 
Design an algorithm to multiply of Large numbers using these 3 methods and analysis which one is best.

a) Conventional  or pen pencil method

b) Polynomial method

c) Divide and conquer method

a) Conventional  or pen pencil method

Algorithm: - multiply 2 numbers

1:  Input: - a, b<- integer="" numbers="" o:p="">  
2:   Output:-multiplication  
3:   Method:-  
4:       Sum=0  
5:         P=0  
6:           While (b! =0) then  
7:               r=r%10  
8:               b=b/10  
9:             Rem =pow (10, p)*r  
10:             Display ‘reminder’  
11:            p++  
12:            s= (a*rem)  
13:             display‘s’  
14:         Sum=sum+s  
15:         i++  
16:           While end  
17:       Display ‘sum’  
18:     Return 0  
19:   Algorithm end  

The time complexity of this algorithm is O(n²)

Table for time complexity:-

n	n2
1	1
2	4
3	9
4	16
5	25
6	36
7	49
8	64
9	81
10	100

b) Polynomial method

Algorithm: Polynomial multiplication

1:  Input:- a,b   
2:          
3:  output:- multiplication of integer numbers  
4:  Method:-  
5:          a0=a/10  
6:          a1=a%10  
7:          b0=b/10  
8:          b1=b/10                              
9:          c2=(a1*b1)*pow(10,2)  
10:          c1=(a0*b1)*pow(10,1)+(a1*bo)*pow(10,1)  
11:          c0=(a0*b0)*pow(10,0)  
12:          result=c2+c1+c0  
13:          display ‘result’  
14:  Algorithm end  

The time complexity of this method is O(n²).

Table for time complexity:-

n	n2
1	1
2	4
3	9
4	16
5	25
6	36
7	49
8	64
9	81
10	100

c) Divide and conquer method

Algorithm:- Long integer Multiplication using Div and Con

                                Function multiply (a , b)

1:  Input:- a,b
3:  Output:- products of integers number  
4:  Method:-  
5:          If n =1           
6:  return ab  
7:  al, ar =leftmost, rightmost [n/2] bits of a  
8:  bl, br= leftmost, rightmost [n/2] bits of b  
9:          p0= multiply(al , bl)  
10:          p2= multiply(ar, br)  
11:          p1= multiply(al+ar)*(bl+br)-(p1+p2)  
12:          return(p2*10n+p1*10n/2+p0*100)  
13:  algorithm ends  

	Div-con mul
n	nlog3
1	1
2	3
3	5.704522
4	9
5	12.81862
6	17.11357
7	21.84986
8	27
9	32.54158
10	38.45586

After finding all the time complexity of the algorithm. We have to find out which is best to do the problem. As per ma discussion of this algorithm, we can conclude that the divide and conquer method is good for solving the problem.

 “divide and conquer method is good for solving the problem.”