1
2 #include "bpol/bitpol-factor.h"
3 #include "bpol/bitpol-squarefree.h"
4 #include "bpol/bitpol-degree.h"
5 #include "bpol/bitpol-print.h"
6
7 #include "bits/bittransforms.h"
8
9 #include "bits/print-bin.h"
10 #include "bits/bitsperlong.h"
11 #include "fxttypes.h"
12 #include "fxtio.h"
13 #include "fxtalloca.h"
14 #include "jjassert.h"
15
16 #include "nextarg.h"
17
18 //% Factorization of binary polynomials.
19
20
21 //#define TIMING // uncomment to disable printing
22
23 int
main(int argc,char ** argv)24 main(int argc, char **argv)
25 {
26 ulong n = 5;
27 NXARG(n, "Degree of polynomials");
28 jjassert( n < BITS_PER_LONG ); // cannot factor
29 ulong cn = 1UL<<n; // leading coeff.
30 ulong np = 0;
31 NXARG(np, "Number of polynomials to factor (0==>up to next degree)");
32 if ( 0==np ) { np = cn; cout << "np=" << np << endl; }
33 uint frm = 0;
34 NXARG(frm, "Output form: 0==>ascii, 1==>coeff-list, 2==>TeX, 3==>bin");
35 // if ( frm>3 ) frm = 0;
36
37 ALLOCA(ulong, f, n); // factors
38 ALLOCA(ulong, e, n); // exponents
39 for (ulong k=0; k<np; ++k)
40 {
41 ulong c = cn + k;
42
43 // c ^= (c>>1); // Gray code order
44 // c = blue_code(c); // blue code order
45
46 ulong fct = bitpol_factor(c, f, e);
47 bitpol_sort_factorization(f, e, fct);
48
49 #ifndef TIMING
50 cout << setw(5) << k << ": ";
51 switch ( frm )
52 {
53 case 0: bitpol_print("", c); break;
54 case 1: bitpol_print_coeff("", c); break;
55 case 2: bitpol_print_tex("", c); break;
56 case 3: bitpol_print_bin("", c); break;
57 }
58 cout << " == ";
59 switch ( frm )
60 {
61 case 0: bitpol_print_factorization("", f, e, fct); break;
62 case 1: bitpol_print_coeff_factorization("", f, e, fct); break;
63 case 2: bitpol_print_tex_factorization("", f, e, fct); break;
64 case 3: bitpol_print_bin_factorization("", f, e, fct); break;
65 case 4: bitpol_print_short_factorization("", f, e, fct); break;
66 }
67
68 cout << endl;
69
70 ulong fi;
71 ulong q = bitpol_test_factorization(c, f, e, fct, fi);
72 if ( q )
73 {
74 cout << "Error " << q << " at factor # " << fi << endl;
75 jjassert( 0 );
76 }
77 #endif // TIMING
78 }
79 #ifdef TIMING
80 cout << " ct=" << np << endl;
81 #endif
82 return 0;
83 }
84 // -------------------------
85
86 /*
87 Timing:
88
89 time ./bin 21
90 arg 1: 21 == n [Degree of polynomials] default=5
91 arg 2: 0 == np [Number of polynomials to factor (0==>up to next degree)] default=0
92 np=2097152
93 arg 3: 0 == frm [Output form: 0==>ascii, 1==>coeff-list, 2==>TeX, 3==>bin] default=0
94 ./bin 21 11.95s user 0.00s system 99% cpu 11.967 total
95 ==> 2097152/11.95 == 175,493 per second
96
97 BENCHARGS=21 0 0
98
99
100 2.2GHz AMD64:
101 ./bin 18 1.09s user 0.02s system 99% cpu 1.108 total
102 ./bin 20 5.14s user 0.02s system 99% cpu 5.170 total
103 ./bin 21 11.05s user 0.05s system 100% cpu 11.093 total
104 ./bin 21 1048576 5.52s user 0.02s system 99% cpu 5.538 total
105 ./bin 24 1048576 6.73s user 0.04s system 99% cpu 6.773 total
106 ./bin 25 1048576 7.14s user 0.04s system 99% cpu 7.194 total
107 ./bin 30 1048576 9.49s user 0.06s system 99% cpu 9.545 total
108 ./bin 31 1048576 9.98s user 0.04s system 99% cpu 10.021 total
109 ./bin 40 1048576 15.12s user 0.07s system 100% cpu 15.188 total
110 ./bin 60 1048576 30.19s user 0.15s system 99% cpu 30.342 total
111
112 2GHz AMD Athlon (32 bit):
113 ./bin 18 2.17s user 0.01s system 99% cpu 2.182 total
114 ./bin 20 7.71s user 0.00s system 99% cpu 7.725 total
115 ./bin 24 1048577 10.62s user 0.00s system 99% cpu 10.629 total
116 ./bin 25 1048576 11.35s user 0.00s system 99% cpu 11.365 total
117 ./bin 30 1048576 15.82s user 0.00s system 99% cpu 15.847 total
118 ./bin 31 1048577 16.75s user 0.01s system 99% cpu 16.782 total
119
120 */
121
122 /// Emacs:
123 /// Local Variables:
124 /// MyRelDir: "demo/gf2n"
125 /// makefile-dir: "../../"
126 /// make-target: "1demo DSRC=demo/gf2n/bitpolfactor-demo.cc"
127 /// make-target2: "1demo DSRC=demo/gf2n/bitpolfactor-demo.cc DEMOFLAGS=-DTIMING"
128 /// End:
129
130