-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtour-time.html
115 lines (93 loc) · 3.01 KB
/
tour-time.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
<html>
<head>
<title>
A Tour of NTL: Some Performance Data </title>
</head>
<center>
<a href="tour-gf2x.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
<a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a>
<a href="tour-roadmap.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>
<h1>
<p align=center>
A Tour of NTL: Some Performance Data
</p>
</h1>
<p> <hr> <p>
Here are some timing figures from using NTL.
They were obtained using NTL 9.6.2 compiled with <tt>g++</tt> 4.2.1
and with GMP 6.1 on a 2.4GHz Intel Core 2 Duo running on Max OSX 10.7.5.
<p>
All times are ins <i>seconds</i>.
The times were obtained using the program <tt>Timing</tt>
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.
<p>
NOTE: that the PRG changed in v9.4.0, so there may be
some inconsistencies.
<p>
<pre>
multiply 1000-bit ints: 5.02504e-07
remainder 2000/1000-bit ints: 1.00513e-06
gcd 1000-bit ints: 1.4485e-05
multiply degree-1000 poly mod 1000-bit prime: 0.0131606
remainder degree-2000/1000 poly mod 1000-bit prime: 0.0381163
preconditioned remainder degree-2000/1000 poly mod 1000-bit prime: 0.0135755
gcd degree-1000 poly mod 1000-bit prime: 0.345835
multiply degree-1000 int poly with 1000-bit coeffs: 0.0225677
factoring degree-1000 poly mod 1000-bit prime...
square-free decomposition...0.346712
factoring multiplicity 1, deg = 1000
computing X^p...22.2213
computing DDF...generating baby steps...+++++++++++++++++++++18.0226
generating giant steps...++++++++++++++++++++++18.8124
giant refine...++++split 1 1
split 2 26
*++++*++++*++++*++++*++*split 0 973
giant refine time: 14.5554
baby refine...split 1 1
split 26 26
split 973 973
baby refine time: 0.000109
DDF time: 51.3992
...total time = 73.9925
multiply 500-bit GF2Xs: 1.29482e-06
remainder 1000/500-bit GF2Xs: 8.38771e-06
gcd 500-bit GF2Xs: 1.54409e-05
factoring degree-500 GF2X: 0.00131092
gcd 500-bit GF2X: 1.54394e-05
multiply degree-500 poly mod 500-bit GF2X: 0.030962
remainder degree-1000/500 poly mod 500-bit GF2X: 0.111182
preconditioned remainder degree-1000/500 poly mod 500-bit GF2X: 0.0622763
gcd degree-500 poly mod 500-bit GF2X: 0.690277
factoring degree-500 poly mod 500-bit GF2X...
square-free decomposition...0.047294
factoring multiplicity 1, deg = 250
computing X^p...6.20889
computing DDF...generating baby steps...++++++++++4.41372
generating giant steps...+++++++++++4.75237
giant refine...++++split 1 9
split 2 13
split 4 44
*++++split 7 73
*split 0 111
giant refine time: 2.94889
baby refine...split 9 9
split 13 13
split 44 44
split 73 73
split 111 111
baby refine time: 0.019359
DDF time: 12.1345
...total time = 18.4086
</pre>
<p>
<center>
<a href="tour-gf2x.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
<a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a>
<a href="tour-roadmap.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>
</body>
</html>