# squaring vs multiply

Zimmermann Paul Paul.Zimmermann at inria.fr
Fri Nov 8 13:57:14 CET 2013

```       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
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:

cassoulet% ./speed -r -s10000000 mpn_mul_n mpn_sqr
overhead 0.000000001 secs, precision 10000 units of 3.13e-10 secs, CPU freq 3200.00 MHz
mpn_mul_n       mpn_sqr
10000000    5.694834027       #0.6679
cassoulet% ./speed -r -s20000000 mpn_mul_n mpn_sqr
overhead 0.000000001 secs, precision 10000 units of 3.13e-10 secs, CPU freq 3200.00 MHz
mpn_mul_n       mpn_sqr
20000000   12.249999000       #0.6664
cassoulet% ./speed -r -s50000000 mpn_mul_n mpn_sqr
overhead 0.000000001 secs, precision 10000 units of 3.13e-10 secs, CPU freq 3200.00 MHz
mpn_mul_n       mpn_sqr
50000000   29.999997000       #0.6699
cassoulet% ./speed -r -s100000000 mpn_mul_n mpn_sqr
overhead 0.000000001 secs, precision 10000 units of 3.13e-10 secs, CPU freq 3200.00 MHz
mpn_mul_n       mpn_sqr
100000000   64.033610693       #0.6729
cassoulet% ./speed -r -s200000000 mpn_mul_n mpn_sqr
overhead 0.000000001 secs, precision 10000 units of 3.13e-10 secs, CPU freq 3200.00 MHz
mpn_mul_n       mpn_sqr
200000000   142.519986000       #0.6565

Any explanation?

Paul
```