What is the fastest way to multiply two integers? 
(from the Prime Pages' list of frequently asked questions)
 New record prime: 274,207,281-1 with 22,338,618 digits by Cooper, Woltman, Kurowski, Blosser & GIMPS (7 Jan 2016).


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>