Home
Search Site
Largest
The 5000
Top 20
Finding
How Many?
Mersenne
Glossary
Prime Curios!
Prime Lists
FAQ
email list
Titans
Submit primes

 Question:
 I would like to know what is currently the fastest algorthim used
to multiply two arbitary long integers. I would also like to know if
the function is available in C/C++.
Yves Gallot replies:
It depends on the size of the numbers:
 up to about 100 digits, the grammarschool method is the fastest
 between 1001,000 digits, the Karatsuba method is the fastest (a recursive
formula that replace 4 multiplications by 3).
 between 1,00010,000,000 digits, convolution based on FFT using some
floatingpoint numbers is the fastest
 for number having more than 10,000,000 digits, multiple Number Theoretic
Transforms and Chinese Remainder Theorem should be used, because accuracy
of floatingpoint numbers of available processors is not large enough.
