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
More information about the gmp-devel
mailing list