Thursday, 28 August 2014

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(n2)
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(n2).
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.”







8 comments:
Write comments
  1. This is very interesting, You're a very skilled blogger.
    I have joined your rss feed and look forward to seeking more of your magnificent post.
    Also, I've shared your site in my social networks!


    Check out my weblog ... local shop

    ReplyDelete
  2. Hi everyone, it's my first visit at this web site, and paragraph is really fruitful in favor
    of me, keep up posting these articles or reviews.

    Also visit my webpage; best dating sites

    ReplyDelete
  3. Sir, the way you explained was really superrrr, keep it up.. :)

    ReplyDelete
  4. I got this web site from my pal who told me about
    this web site and now this time I am visiting this web site and reading
    very informative posts here.

    Also visit my web page: diet plans for Women to lose weight (http://dietplansforwomentoloseweightfast.com)

    ReplyDelete
  5. Excellent post. I definitely appreciate this site. Thanks!


    Here is my webpage Minecraft.net

    ReplyDelete
  6. time complexity explained nicely,. good post

    ReplyDelete
  7. Quality articles is the key to interest the users to go to see the site, that's what this website is providing...

    ReplyDelete
  8. Thanks for finally writing about multipkication of large no's

    ReplyDelete

Featured post

List of Universities in Karnataka offering M.Sc Computer Science

The post-graduate programme in Computer Science (M.Sc Computer Science) contains two academic years duration and having a four semesters....

Popular Posts

Copyright @ 2011-2016