# how multiply two large numbers stored in arrays?

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!!

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

I hope this helps!!

Best regards,

Bruno

2 Likes