Hi,
asymptotically, the cost of a squaring by FFT should be at least 2/3 of the
cost of a multiply, since a multiply performs 3 transforms and 1 pointwise
multiplication, whereas a squaring saves 1 transform.
Moreover GMP is using Schönhage-Strassen's algorithms, where the pointwise
Zimmermann Paul paul.zimmerm...@inria.fr writes:
Moreover GMP is using Schönhage-Strassen's algorithms, where the pointwise
multiplications are not negligible, thus we should have a ratio well above
2/3.
However in GMP 5.1.3 the ratio is around 2/3, and sometimes even below:
Any