1 | |
---|
2 | #include <NTL/GF2X.h> |
---|
3 | |
---|
4 | NTL_CLIENT |
---|
5 | |
---|
6 | struct wd { |
---|
7 | int amt; |
---|
8 | |
---|
9 | wd(int x) { amt = x; } |
---|
10 | }; |
---|
11 | |
---|
12 | #define WD(x,y) wd(x) << (y) |
---|
13 | |
---|
14 | ostream& operator<<(ostream& s, const wd& w) |
---|
15 | { |
---|
16 | s.width(w.amt); |
---|
17 | return s; |
---|
18 | } |
---|
19 | |
---|
20 | int main() |
---|
21 | { |
---|
22 | long n; |
---|
23 | GF2X a, b, c, c1, ss, ss1, tt, tt1; |
---|
24 | double t; |
---|
25 | long iter, i; |
---|
26 | |
---|
27 | cout << WD(12,"n") << WD(12,"OldGCD") << WD(12,"GCD") << WD(12,"OldXGCD") |
---|
28 | << WD(12, "XGCD") << "\n"; |
---|
29 | |
---|
30 | cout.precision(3); |
---|
31 | cout.setf(ios::scientific); |
---|
32 | |
---|
33 | |
---|
34 | for (n = 32; n <= (1L << 18); n = n << 1) { |
---|
35 | random(a, n); |
---|
36 | random(b, n); |
---|
37 | OldGCD(c, a, b); |
---|
38 | GCD(c1, a, b); |
---|
39 | OldXGCD(c, ss, tt, a, b); |
---|
40 | XGCD(c1, ss1, tt1, a, b); |
---|
41 | if (c1 != c || ss1 != ss || tt1 != tt) { |
---|
42 | cerr << "**** GF2XTest FAILED!\n"; |
---|
43 | return 1; |
---|
44 | } |
---|
45 | |
---|
46 | cout << WD(12,n); |
---|
47 | |
---|
48 | iter = 0; |
---|
49 | do { |
---|
50 | iter = iter ? (2*iter) : 1; |
---|
51 | t = GetTime(); |
---|
52 | for (i = 0; i < iter; i++) |
---|
53 | OldGCD(c, a, b); |
---|
54 | t = GetTime()-t; |
---|
55 | } while (t < 0.5); |
---|
56 | |
---|
57 | cout << WD(12,t/iter); |
---|
58 | |
---|
59 | iter = 0; |
---|
60 | do { |
---|
61 | iter = iter ? (2*iter) : 1; |
---|
62 | t = GetTime(); |
---|
63 | for (i = 0; i < iter; i++) |
---|
64 | GCD(c, a, b); |
---|
65 | t = GetTime()-t; |
---|
66 | } while (t < 0.5); |
---|
67 | |
---|
68 | cout << WD(12,t/iter); |
---|
69 | |
---|
70 | iter = 0; |
---|
71 | do { |
---|
72 | iter = iter ? (2*iter) : 1; |
---|
73 | t = GetTime(); |
---|
74 | for (i = 0; i < iter; i++) |
---|
75 | OldXGCD(c, ss, tt, a, b); |
---|
76 | t = GetTime()-t; |
---|
77 | } while (t < 0.5); |
---|
78 | |
---|
79 | cout << WD(12,t/iter); |
---|
80 | |
---|
81 | iter = 0; |
---|
82 | do { |
---|
83 | iter = iter ? (2*iter) : 1; |
---|
84 | t = GetTime(); |
---|
85 | for (i = 0; i < iter; i++) |
---|
86 | XGCD(c, ss, tt, a, b); |
---|
87 | t = GetTime()-t; |
---|
88 | } while (t < 0.5); |
---|
89 | |
---|
90 | cout << WD(12,t/iter); |
---|
91 | |
---|
92 | cout << "\n"; |
---|
93 | } |
---|
94 | |
---|
95 | return 0; |
---|
96 | } |
---|