1 '''
2 Bit reversal algorithm performance comparison
3 Bracewell-Buneman, Yu-Loh-Miller
4 John Bryan, 2018
5 Python 2.7.3
6 '''
7 import numpy as np
8 import matplotlib.pyplot as plt
9 import time
10 import warnings
11 np.set_printoptions(threshold = np.nan, precision = 6, suppress = 1)
12 warnings.filterwarnings("ignore")
13
14
15 def yu_loh_miller(xarray, radix, log2length, length):
16 '''
17 Yu-Loh-Miller digit-reversal function
18 inputs: xarray is input array; radix = 2 for single binary bit reversal;
19 log2length = log2(xarray length); length = xarray length.
20 output: digit-reversed array xarray.
21 '''
22 if log2length % 2 == 0:
23 n1var = int(np.sqrt(length))
24 else:
25 n1var = int(np.sqrt(int(length/radix)))
26
27 reverse = np.zeros(n1var, dtype = int)
28 reverse[1] = int(length/radix)
29 for jvar in range(1, radix):
30 reverse[jvar] = reverse[jvar-1]+reverse[1]
31 for i in range(1, int(n1var/radix)):
32 reverse[radix*i] = int(reverse[i]/radix)
33 for jvar in range(1, radix):
34 reverse[int(radix*i)+jvar] = reverse[int(radix*i)]+reverse[jvar]
35
36 for i in range(0, n1var-1):
37 for jvar in range(i+1, n1var):
38 uvar = i+reverse[jvar]
39 vvar = jvar+reverse[i]
40
41 temp = xarray[uvar]
42 xarray[uvar] = xarray[vvar]
43 xarray[vvar] = temp
44 if log2length % 2 == 1:
45 for zvar in range(1, radix):
46 uvar = i+reverse[jvar]+(zvar*n1var)
47 vvar = jvar+reverse[i]+(zvar*n1var)
48
49 temp = xarray[uvar]
50 xarray[uvar] = xarray[vvar]
51 xarray[vvar] = temp
52
53 return xarray
54
55
56 def bracewell_buneman(xarray, length, log2length):
57 '''
58 bracewell-buneman bit reversal function
59 inputs: xarray is array; length is array length; log2length=log2(length).
60 output: bit reversed array xarray.
61 '''
62 muplus = int((log2length+1)/2)
63 mvar = 1
64 reverse = np.zeros(length, dtype = int)
65 upper_range = muplus+1
66 for nuvar in np.arange(1, upper_range):
67 for kvar in np.arange(0, mvar):
68 tvar = 2*reverse[kvar]
69 reverse[kvar] = tvar
70 reverse[kvar+mvar] = tvar+1
71 mvar = mvar+mvar
72 if (log2length & 0x01):
73 mvar = mvar/2
74 for qvar in np.arange(1, mvar):
75 nprime = qvar-mvar
76 rprimeprime = reverse[qvar]*mvar
77 for pvar in np.arange(0, reverse[qvar]):
78 nprime = nprime+mvar
79 rprime = rprimeprime+reverse[pvar]
80 temp = xarray[nprime]
81 xarray[nprime] = xarray[rprime]
82 xarray[rprime] = temp
83 return xarray
84
85
86 def plot_times(bbtimes, ylmtimes):
87 '''
88 Plots bit-reversal time measurements vs sequence lengths.
89 Inputs are bbtimes, the time measurement array for Bracewell-Buneman;
90 ylmtimes, the time measurement array for Yu-Loh-Miller.
91 No ouputs.
92 '''
93 uvar = np.zeros(9, dtype = int)
94 for i in range(4, 13):
95 uvar[i-4] = np.power(2, i)
96 plt.figure(figsize = (7, 5))
97 plt.rc("font", size = 9)
98 plt.loglog(uvar, ylmtimes*1000, 'o', ms = 5, markerfacecolor = "None", \
99 markeredgecolor = 'blue', markeredgewidth = 1, \
100 basex = 2, basey = 10, label = 'Yu-Loh-Miller')
101 plt.loglog(uvar, bbtimes*1000, '^', ms = 5, markerfacecolor = "None", \
102 markeredgecolor = 'green', markeredgewidth = 1, \
103 basex = 2, basey = 10, label = 'Bracewell-Buneman ')
104 plt.legend(loc = 2)
105 plt.grid()
106 plt.xlim([9, 6000])
107 plt.ylim([.01, 100])
108 plt.ylabel("time (milliseconds)")
109 plt.xlabel("sequence length")
110 plt.title("Bit Reversal Performance Comparison in Python")
111 axx = plt.gca()
112 plt.rcParams['axes.facecolor'] = '0.7'
113 plt.rcParams['axes.edgecolor'] = '0.7'
114 axx.set_axis_bgcolor('0.7')
115 axx.patch.set_facecolor('0.7')
116 axx.patch.set_edgecolor('0.7')
117 plt.savefig('bitreversal.png', facecolor = '0.7')
118 plt.show()
119 return None
120
121
122 def test():
123 '''
124 Test bit reversal performance.
125 inputs: none.
126 outputs: performance measurements for the two bit reversal algorithms.
127 '''
128 i = 0
129 iterations = 1000
130 times2 = np.zeros(9)
131 times3 = np.zeros(9)
132 for log2length in range (4, 13):
133 number_left = 13-log2length
134 print number_left, " sequence length(s) left to test"
135 sum2 = 0
136 sum3 = 0
137 length = np.power(2, log2length)
138 for svar in np.arange(0, iterations):
139 np.random.seed(0)
140 x2array = np.random.rand(2*length).view(np.complex_)
141 np.random.seed(0)
142 x3array = np.random.rand(2*length).view(np.complex_)
143 time2 = time.time()
144 x2array = bracewell_buneman(x2array, length, log2length)
145 difference = time.time()-time2
146 sum2 = sum2+difference
147 time3 = time.time()
148 x2array = yu_loh_miller(x2array, 2, log2length, length)
149 difference = time.time()-time3
150 sum3 = sum3+difference
151 times2[i] = sum2/iterations
152 times3[i] = sum3/iterations
153
154 t_f = np.array_equal(x3array, x2array)
155
156 assert(t_f)
157 i = i+1
158 return times2, times3
159
160
161 def testbench():
162 '''
163 Test and plot bit reversal performance.
164 inputs: none.
165 outputs: none.
166 '''
167 times2, times3 = test()
168 plot_times(times2, times3)
169 return None
170
171
172 testbench()