# How Fast Can You Multiply Really Big Numbers? [Snippet]

### Have you ever considered this common but taken-for-granted question? How does it compare to how fast computers can do it?

Join the DZone community and get the full member experience.

Join For FreeHow long does it take to multiply very large integers? Using the algorithm you learned in elementary school, it takes O(*n*²) operations to multiply two *n* digit numbers. But for large enough numbers it pays to carry out multiplication very differently, using FFTs.

If you’re multiplying integers with tens of thousands of decimal digits, the most efficient algorithm is the Schönhage-Strassen algorithm, which takes

O(*n* log *n* log log *n*)

operations. For smaller numbers, another algorithm, such as Karatsuba’s algorithm, might be faster. And for impractically large numbers, Fürer’s algorithm is faster.

What is impractically large? Let’s say a number is impractically large if storing it requires more than a billion dollars worth of RAM. If I did my back-of-the-envelop math correctly, you can buy enough RAM to store about 2^{57} bits for about a billion dollars. The Schönhage-Strassen algorithm is more efficient than Fürer’s algorithm for numbers with less than 2^{64} bits.

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments