1
2 // demo-is-self-contained
3
4 #include "nextarg.h"
5 #include "perm/revbinpermute.h" // revbin_permute()
6 #include "aux0/swap.h" // swap2()
7 #include "bits/print-bin.h" // print_bin()
8
9 #include "fxttypes.h"
10 #include "jjassert.h"
11 #include "fxtio.h"
12
13 //% Recursive revbin-permutation routine.
14 // Based on code by Udayan Kale <udayan (AT) pdaelegance (DOT) com>
15
16
17 //#define TIMING // uncomment to disable printing
18
19 template <typename Type>
bitrev(Type * p,ulong i,ulong l,ulong r,ulong k)20 void bitrev(Type* p, ulong i, ulong l, ulong r, ulong k)
21 {
22 ulong m = (l+r)>>1;
23 if ( m>i ) swap2(p[m], p[i]);
24 else return;
25 bitrev(p, i+k, l, m, k<<1);
26 bitrev(p, i+2*k, m, r, k<<1);
27 }
28 // -------------------------
29
30
bitrev_p(ulong i,ulong l,ulong r,ulong k,ulong ind=0)31 void bitrev_p(ulong i, ulong l, ulong r, ulong k, ulong ind=0)
32 {
33 ulong m = (l+r)>>1;
34 if ( m<=i ) return;
35
36 print_bin(" ", m, 8);
37 for (ulong j=0; j<ind; ++j) cout << " ";
38 cout << " i=" << i << " m=" << m; // << " l=" << l << " r=" << r << " k=" << k;
39
40 // if ( m>i ) cout << " SWAP"; // swap2(p[m], p[i]);
41 cout << endl;
42
43 // if ( m<=i ) return;
44 // if ( m-l <= 1 ) return;
45
46 bitrev_p(i+k, l, m, k<<1, ind+1);
47 bitrev_p(i+2*k, m, r, k<<1, ind+1);
48 }
49 // -------------------------
50
51 template <typename Type>
is_seq(const Type * dst,ulong n,Type start=0,Type step=1)52 inline bool is_seq(const Type *dst, ulong n, Type start=0, Type step=1)
53 // Check whether array elements are the sequence
54 // start, start+step, start+2*step, ...
55 // (as filled in by set_seq(dst, n, start, step)
56 {
57 for (ulong k=0; k<n; ++k, start += step)
58 if ( dst[k] != start ) return false;
59 return true;
60 }
61 // -------------------------
62
63 int
main(int argc,char ** argv)64 main(int argc, char **argv)
65 {
66 ulong ldn = 6;
67 NXARG(ldn, "log_2(n) where n is the length of the array");
68 ulong n = 1UL << ldn;
69 #ifdef TIMING
70 ulong kk = 1024;
71 NXARG(kk, "Number of times to permute");
72 bool q = 0;
73 NXARG(q, "0==>FXT's revbin_permute(), 1==>recursive routine()");
74 #endif
75
76 double* f = new double[n];
77 for (ulong k=0; k<n; ++k) f[k] = (double)k;
78
79 #ifndef TIMING
80 bitrev_p(1, 0, n, 1); // print call graph
81 for (ulong k=0; k<n; ++k) f[k] = (double)k;
82 revbin_permute(f, n);
83 bitrev(f, 1, 0, n, 1);
84 jjassert( is_seq(f, n) );
85 #else
86 if ( q ) for (ulong k=0; k<kk; ++k) bitrev(f, 1, 0, n, 1);
87 else for (ulong k=0; k<kk; ++k) revbin_permute(f, n);
88 #endif
89
90 delete [] f;
91 return 0;
92 }
93 // -------------------------
94
95 //./bin 20 10 0 0.87s user 0.01s system 100% cpu 0.876 total // revbin_permute()
96 //./bin 20 10 1 1.38s user 0.01s system 99% cpu 1.402 total // bitrev()
97
98 //./bin 8 1000000 0 0.86s user 0.00s system 99% cpu 0.866 total // revbin_permute()
99 //./bin 8 1000000 1 2.56s user 0.00s system 99% cpu 2.562 total // bitrev()
100
101 /// Emacs:
102 /// Local Variables:
103 /// MyRelDir: "demo/perm"
104 /// makefile-dir: "../../"
105 /// make-target: "1demo DSRC=demo/perm/revbin-perm-rec-demo.cc"
106 /// make-target2: "1demo DSRC=demo/perm/revbin-perm-rec-demo.cc DEMOFLAGS=-DTIMING"
107 /// End:
108
109