[Previous] [Up] [Next]

A Tour of NTL: Some Performance Data


Here are some timing figures from using NTL. They were obtained using NTL 8.1 compiled with g++ 4.2.1 and with GMP 5.1 on a 2.8GHz Intel Core 2 Duo running on Max OSX 10.6.8.

All times are ins seconds. The times were obtained using the program Timing included in the distribution. The data was generated using NTL's random number generator, but running this on a different machine should (in theory) generate the same data.


multiply 1000-bit ints: 4.46701e-07
remainder 2000/1000-bit ints: 8.29764e-07
gcd 1000-bit ints: 1.05475e-05
multiply degree-1000 poly mod 1000-bit prime: 0.0158512
remainder degree-2000/1000 poly mod 1000-bit prime: 0.0443398
preconditioned remainder degree-2000/1000 poly mod 1000-bit prime: 0.0161609
gcd degree-1000 poly mod 1000-bit prime: 0.373181
multiply degree-1000 int poly with 1000-bit coeffs: 0.0162288

factoring degree-1000 poly mod 1000-bit prime...
square-free decomposition...0.37455
factoring multiplicity 1, deg = 1000
computing X^p...25.7909
computing DDF...generating baby steps...+++++++++++++++++++++17.7092
generating giant steps...++++++++++++++++++++++18.5104
giant refine...++++split 1 43
split 2 38
split 3 64
*++++split 5 108
*++++split 11 237
split 12 510
*giant refine time: 9.17354
baby refine...split 3 6
split 6 6
split 9 9
split 22 22
split 38 38
split 64 64
split 108 108
split 237 237
split 248 248
split 262 262
baby refine time: 0.684972
DDF time: 46.0867
computing EDF(3,2)...+0.076714
...total time = 72.3618

multiply 500-bit GF2Xs: 1.02563e-06
remainder 1000/500-bit GF2Xs: 6.59219e-06
gcd 500-bit GF2Xs: 1.19024e-05

factoring degree-500 GF2X: 0.00108709
gcd 500-bit GF2X: 1.1894e-05
multiply degree-500 poly mod 500-bit GF2X: 0.0246443
remainder degree-1000/500 poly mod 500-bit GF2X: 0.0884585
preconditioned remainder degree-1000/500 poly mod 500-bit GF2X: 0.0492777
gcd degree-500 poly mod 500-bit GF2X: 0.554326

factoring degree-500 poly mod 500-bit GF2X...
square-free decomposition...0.038124
factoring multiplicity 1, deg = 250
computing X^p...4.94016
computing DDF...generating baby steps...++++++++++3.51031
generating giant steps...+++++++++++3.78488
giant refine...++++*++++split 6 59
split 7 68
*split 0 123
giant refine time: 2.59672
baby refine...split 59 59
split 68 68
split 123 123
baby refine time: 3.1e-05
DDF time: 9.89211

...total time = 14.8848


[Previous] [Up] [Next]