Yves Gallot replies:
- 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++.
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.