source: git/ntl/src/QuickTest.c @ 287cc8

spielwiese
Last change on this file since 287cc8 was 287cc8, checked in by Hans Schönemann <hannes@…>, 14 years ago
ntl 5.5.2 git-svn-id: file:///usr/local/Singular/svn/trunk@12402 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.1 KB
Line 
1
2#include <NTL/ZZ_pX.h>
3#include <NTL/lzz_pX.h>
4#include <NTL/GF2X.h>
5
6#include <NTL/version.h>
7
8NTL_CLIENT
9
10
11#define make_string_aux(x) #x
12#define make_string(x) make_string_aux(x)
13
14int SmallModulusTest(long p, long n)
15{
16   zz_pBak bak;
17
18   bak.save();
19
20
21   zz_p::init(p);
22
23   zz_pX a, b, c, cc;
24
25   random(a, n);
26   random(b, n);
27   PlainMul(c, a, b);
28   FFTMul(cc, a, b);
29
30   int res;
31   res = (c != cc);
32
33   bak.restore();
34
35   return res;
36}
37
38
39int GF2X_test()
40{
41   GF2X a, b, c, c1;
42
43   long n;
44
45#ifdef NTL_GF2X_LIB
46   for (n = 32; n <= (1L << 18); n = n << 1) {
47      random(a, n);
48      random(b, n);
49      OldMul(c, a, b);
50      mul(c1, a, b);
51      if (c1 != c) return 1;
52   }
53#endif
54
55   return 0;
56}
57
58void GF2X_time()
59{
60   long n = 1000000L;
61   long iter;
62
63   GF2X a, b, c;
64
65   double t;
66   long i;
67
68   random(a, n);
69   random(b, n);
70
71   mul(c, a, b);
72
73   iter = 0;
74   do {
75      iter = iter ? (2*iter) : 1;
76      t = GetTime();
77      for (i = 0; i < iter; i++)
78         mul(c, a, b);
79      t = GetTime() - t;
80   } while (t < 0.5);
81
82   cerr << "time to multiply polynomials over GF(2) \n   of degree < 1000000: "
83        << (t/iter) << "s\n";
84
85#ifdef NTL_GF2X_LIB
86   OldMul(c, a, b);
87
88   iter = 0;
89   do {
90      iter = iter ? (2*iter) : 1;
91      t = GetTime();
92      for (i = 0; i < iter; i++)
93         OldMul(c, a, b);
94      t = GetTime() - t;
95   } while (t < 0.5);
96
97   cerr << "   **** using old code: "  << (t/iter) << "s\n";
98#endif
99
100}
101
102
103int main()
104{
105
106
107   cerr << "This is NTL version " << NTL_VERSION << "\n";
108
109   cerr << "Basic Configuration Options:\n";
110
111
112#ifdef NTL_STD_CXX
113   cerr << "NTL_STD_CXX\n";
114#endif
115
116#ifdef NTL_PSTD_NNS
117   cerr << "NTL_PSTD_NNS\n";
118#endif
119
120#ifdef NTL_PSTD_NHF
121   cerr << "NTL_PSTD_NHF\n";
122#endif
123
124#ifdef NTL_PSTD_NTN
125   cerr << "NTL_PSTD_NTN\n";
126#endif
127
128#ifdef NTL_GMP_LIP
129   cerr << "NTL_GMP_LIP\n";
130#endif
131
132#ifdef NTL_GMP_HACK
133   cerr << "NTL_GMP_HACK\n";
134#endif
135
136#ifdef NTL_GF2X_LIB
137   cerr << "NTL_GF2X_LIB\n";
138#endif
139
140
141#ifdef NTL_LONG_LONG_TYPE
142   cerr << "NTL_LONG_LONG_TYPE: ";
143   cerr << make_string(NTL_LONG_LONG_TYPE) << "\n";
144#endif
145
146#ifdef NTL_UNSIGNED_LONG_LONG_TYPE
147   cerr << "NTL_UNSIGNED_LONG_LONG_TYPE: ";
148   cerr << make_string(NTL_UNSIGNED_LONG_LONG_TYPE) << "\n";
149#endif
150
151#ifdef NTL_CXX_ONLY
152   cerr << "NTL_CXX_ONLY\n";
153#endif
154
155
156#ifdef NTL_X86_FIX
157   cerr << "NTL_X86_FIX\n";
158#endif
159
160#ifdef NTL_NO_X86_FIX
161   cerr << "NTL_NO_X86_FIX\n";
162#endif
163
164#ifdef NTL_NO_INIT_TRANS
165   cerr << "NTL_NO_INIT_TRANS\n";
166#endif
167
168#ifdef NTL_CLEAN_INT
169   cerr << "NTL_CLEAN_INT\n";
170#endif
171
172#ifdef NTL_CLEAN_PTR
173   cerr << "NTL_CLEAN_PTR\n";
174#endif
175
176#ifdef NTL_RANGE_CHECK
177   cerr << "NTL_RANGE_CHECK\n";
178#endif
179
180
181cerr << "\n";
182cerr << "Resolution of double-word types:\n";
183cerr << make_string(NTL_LL_TYPE) << "\n";
184cerr << make_string(NTL_ULL_TYPE) << "\n";
185
186
187cerr << "\n";
188cerr << "Performance Options:\n";
189
190#ifdef NTL_LONG_LONG
191   cerr << "NTL_LONG_LONG\n";
192#endif
193
194#ifdef NTL_AVOID_FLOAT
195   cerr << "NTL_AVOID_FLOAT\n";
196#endif
197
198#ifdef NTL_SPMM_UL
199   cerr << "NTL_SPMM_UL\n";
200#endif
201
202
203#ifdef NTL_SPMM_ULL
204   cerr << "NTL_SPMM_ULL\n";
205#endif
206
207
208#ifdef NTL_SPMM_ASM
209   cerr << "NTL_SPMM_ASM\n";
210#endif
211
212
213
214
215#ifdef NTL_AVOID_BRANCHING
216   cerr << "NTL_AVOID_BRANCHING\n";
217#endif
218
219
220
221#ifdef NTL_TBL_REM
222   cerr << "NTL_TBL_REM\n";
223#endif
224
225
226#ifdef NTL_GF2X_ALTCODE
227   cerr << "NTL_GF2X_ALTCODE\n";
228#endif
229
230#ifdef NTL_GF2X_ALTCODE1
231   cerr << "NTL_GF2X_ALTCODE1\n";
232#endif
233
234
235#ifdef NTL_GF2X_NOINLINE
236   cerr << "NTL_GF2X_NOINLINE\n";
237#endif
238
239   cerr << "\n\n";
240
241   if (_ntl_gmp_hack)
242      cerr << "using GMP hack\n\n";
243
244   cerr << "running tests...";
245
246   long n, k;
247
248   n = 200;
249   k = 10*NTL_ZZ_NBITS;
250
251   ZZ p;
252
253   GenPrime(p, k);
254
255
256   ZZ_p::init(p);         // initialization
257
258   ZZ_pX f, g, h, r1, r2, r3;
259
260   random(g, n);    // g = random polynomial of degree < n
261   random(h, n);    // h =             "   "
262   random(f, n);    // f =             "   "
263
264   // SetCoeff(f, n);  // Sets coefficient of X^n to 1
265
266   ZZ_p lc;
267
268   do {
269      random(lc);
270   } while (IsZero(lc));
271
272   SetCoeff(f, n, lc);
273
274
275   // For doing arithmetic mod f quickly, one must pre-compute
276   // some information.
277
278   ZZ_pXModulus F;
279   build(F, f);
280
281   PlainMul(r1, g, h);  // this uses classical arithmetic
282   PlainRem(r1, r1, f);
283
284   MulMod(r2, g, h, F);  // this uses the FFT
285
286   MulMod(r3, g, h, f);  // uses FFT, but slower
287
288   // compare the results...
289
290   if (r1 != r2) {
291      cerr << "r1 != r2!!\n";
292      return 1;
293   }
294   else if (r1 != r3) {
295      cerr << "r1 != r3!!\n";
296      return 1;
297   }
298
299
300   // small prime tests...I've made some changes in v5.3
301   // that should be checked on various platforms, so
302   // we might as well check them here.
303
304   if (SmallModulusTest(17, 1000)) {
305      cerr << "first SmallModulusTest failed!!\n";
306      return 1;
307   }
308
309   if (SmallModulusTest((1L << (NTL_SP_NBITS))-1, 1000)) {
310      cerr << "second SmallModulusTest failed!!\n";
311      return 1;
312   }
313
314   // Test gf2x code....
315
316   if (GF2X_test()) {
317      cerr << "GF2X test failed!\n";
318      return 1;
319   }
320
321
322   cerr << "OK\n";
323
324   ZZ x1, x2, x3, x4;
325   double t;
326   long i;
327
328   RandomLen(x1, 1024);
329   RandomBnd(x2, x1);
330   RandomBnd(x3, x1);
331
332   mul(x4, x2, x3);
333
334   t = GetTime();
335   for (i = 0; i < 100000; i++)
336      mul(x4, x2, x3);
337   t = GetTime()-t;
338
339   cerr << "time for 1024-bit mul: " << t*10 << "us";
340
341   if (_ntl_gmp_hack) {
342      _ntl_gmp_hack = 0;
343      mul(x4, x2, x3);
344
345      t = GetTime();
346      for (i = 0; i < 100000; i++)
347         mul(x4, x2, x3);
348      t = GetTime()-t;
349
350      cerr << " (" << (t*10) << "us without GMP)";
351
352      _ntl_gmp_hack = 1;
353   }
354
355   cerr << "\n";
356
357   rem(x2, x4, x1);
358
359   t = GetTime();
360   for (i = 0; i < 100000; i++)
361      rem(x2, x4, x1);
362   t = GetTime()-t;
363
364   cerr << "time for 2048/1024-bit rem: " << t*10 << "us";
365
366   if (_ntl_gmp_hack) {
367      _ntl_gmp_hack = 0;
368      rem(x2, x4, x1);
369
370      t = GetTime();
371      for (i = 0; i < 100000; i++)
372         rem(x2, x4, x1);
373      t = GetTime()-t;
374      cerr << " (" << (t*10) << "us without GMP)";
375
376      _ntl_gmp_hack = 1;
377   }
378
379   cerr << "\n";
380
381
382   GenPrime(p, 1024);
383   RandomBnd(x1, p);
384   if (IsZero(x1)) set(x1);
385
386   InvMod(x2, x1, p);
387
388   t = GetTime();
389   for (i = 0; i < 1000; i++)
390      InvMod(x2, x1, p);
391   t = GetTime()-t;
392
393   cerr << "time for 1024-bit modular inverse: " << t*1000 << "us";
394
395   if (_ntl_gmp_hack) {
396      _ntl_gmp_hack = 0;
397      InvMod(x2, x1, p);
398
399      t = GetTime();
400      for (i = 0; i < 1000; i++)
401         InvMod(x2, x1, p);
402      t = GetTime()-t;
403         cerr << " (" << (t*1000) << "us without GMP)";
404
405      _ntl_gmp_hack = 1;
406   }
407
408   cerr << "\n";
409
410
411
412   // test modulus switching
413
414   n = 1024;
415   k = 1024;
416   RandomLen(p, k);
417
418   ZZ_p::init(p);
419   ZZ_pInfo->check();
420
421   ZZ_pX j1, j2, j3;
422
423   random(j1, n);
424   random(j2, n);
425
426   t = GetTime();
427   for (i = 0; i < 20; i++) mul(j3, j1, j2);
428   t = GetTime()-t;
429
430   cerr << "time to multiply degree 1023 polynomials\n   modulo a 1024-bit number: ";
431   cerr << (t/20) << "s";
432
433   if (_ntl_gmp_hack) {
434      _ntl_gmp_hack = 0;
435
436      ZZ_p::init(p);
437      ZZ_pInfo->check();
438
439      t = GetTime();
440      for (i = 0; i < 20; i++) mul(j3, j1, j2);
441      t = GetTime()-t;
442
443      cerr << " (" << (t/20) << "s without GMP)";
444      _ntl_gmp_hack = 1;
445   }
446
447   cerr << "\n";
448
449   GF2X_time();
450
451   return 0;
452}
Note: See TracBrowser for help on using the repository browser.