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 gradeschool 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 abacususer will sum the products as soon as each one is computed. The standard procedure for multiplication of two ndigit numbers requires a number of elementary operations proportional to n^2, or Theta(n^2)! in the bigO 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 penandpencil algorithm for multiplying two ndigit 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^{2})
Table for time complexity:
n

n^{2}

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^{2}).
Table for time complexity:
n

n^{2}

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
Divcon mul
 
n

n^{log3}

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.
This is very interesting, You're a very skilled blogger.
ReplyDeleteI 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
Hi everyone, it's my first visit at this web site, and paragraph is really fruitful in favor
ReplyDeleteof me, keep up posting these articles or reviews.
Also visit my webpage; best dating sites
Sir, the way you explained was really superrrr, keep it up.. :)
ReplyDeleteI got this web site from my pal who told me about
ReplyDeletethis 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)
Excellent post. I definitely appreciate this site. Thanks!
ReplyDeleteHere is my webpage Minecraft.net
time complexity explained nicely,. good post
ReplyDeleteQuality articles is the key to interest the users to go to see the site, that's what this website is providing...
ReplyDeleteThanks for finally writing about multipkication of large no's
ReplyDelete