4 ms·
It's mostly a theoretical result. The previous FFT-based multiplication algorithms (including the one in GMP) all have almost linear complexity. For integers th
by fdej 12y ago
It's mostly a theoretical result. The previous FFT-based multiplication algorithms (including the one in GMP) all have almost linear complexity. For integers that can be stored within the observable universe, overhead and memory locality matter much more than nested logarithmic factors in the asymptotic complexity bound. It's conceivable that the new algorithm is superior in the real world, but nothing really suggests that it should be.