What is the fastest way to multiply two integers? 
(from the Prime Pages' list of frequently asked questions)
 New record prime (GIMPS): 282,589,933-1 with 24,862,048 digits by P. Laroche, G. Woltman, A. Blosser, et al. (7 Dec 2018).


Home
Search Site

Largest
The 5000
Top 20
Finding
How Many?
Mersenne

Glossary
Prime Curios!
Prime Lists

FAQ
e-mail 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 grammar-school method is the fastest
  • between 100-1,000 digits, the Karatsuba method is the fastest (a recursive formula that replace 4 multiplications by 3).
  • between 1,000-10,000,000 digits, convolution based on FFT using some floating-point 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 floating-point numbers of available processors is not large enough.
The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>