NTT multiplication.

Paul Zimmermann Paul.Zimmermann at loria.fr
Wed May 13 10:23:54 CEST 2009


> This is excellent, but still not anywhere the 2.3 factor I had expected:
> http://magma.maths.usyd.edu.au/users/allan/intmult.html

to be honest, 10^6 limbs is the first value I tried (for historical reasons),
and is also the best I've found so far:

        Vanilla GMP 4.3.0  With our code    Ratio
100000    0.038994000      0.036994000      1.05
200000    0.094985000      0.074988000      1.27
500000    0.210968000      0.200969000      1.05
1000000   0.534919000      0.391940000      1.36
2000000   1.161824000      0.986850000      1.18
5000000   3.362489000      2.913557000      1.15
10000000  7.150913000      6.394028000      1.12

Note this 2nd experiment gives 1.36 instead of 1.45 for 10^6, thus figures are
not very reliable, but our code seems consistently faster.

Paul







More information about the gmp-devel mailing list