how multiply two large numbers stored in arrays?

general
,
1

I found a very good algorithm to multiply two numbers if one of them is very large…
It is very nicely explained in the followng Codechef tutorial!!


but the following problem in spoj requires the algorithm to multiply if both of them are large!!

please help me if anybody solved the above problem! :slight_smile:
2

Hello,

Possibly, the “good algorithm” you’ve found to solve the Small-Factorials problem, involves some grade-school mathematics, and, it has the “bad” characteristic that its running time is quadratic, as it needs to iterate over both numbers in order to get the result correct.

An amazing idea to multiply big numbers “fast”, is the idea of using what is usually known as “the most important numerical algorithm” of our lifetime, and that is, the FFT algorithm.

The mathematics behind it, is, by far, the most beautiful thing I’ve ever seen in my life and, when I have all the time and knowledge I will for sure write a tutorial about this!

In the meantime, maybe you can use google translate, to try and understand this tutorial :smiley:

I hope this helps!!

Best regards,

Bruno

2 Likes
3

Karatsuba algorithm can be helpful…
read this http://rishabhsays.wordpress.com/2010/07/07/karatsuba-multiplication/
its very helpful … :slight_smile:

4

If it’s not mandatory to use arrays , then you can try using BigInteger in java(May be u won’t get TLE with that).and that will save you from writing complex algorithms.

1 Like