Bit-reversal permutation: Difference between revisions

Revision as of 23:21, 18 October 2018

Revision as of 19:59, 14 February 2019

Line 25:

| last4 = Ruskey | first4 = Frank

| doi = 10.1016/j.ipl.2013.02.017

| issue = 10-1110–11

| journal = Information Processing Letters

| mr = 3037467

Line 35:

There are two extensions of the bit-reversal permutation to sequences of arbitrary length. These extensions coincide with bit-reversal for sequences whose length is a power of 2, and their purpose is to separate adjacent items in a sequence for the efficient operation of the [[Kaczmarz method|Kaczmarz algorithm]]. The first of these extensions, called ''Efficient Ordering''<ref>{{cite book|last1=Herman|first1=Gabor T.|author1-link=Gabor Herman|title=Fundamentals of Computerized Tomography|date=2009|publisher=Springer|___location=London|isbn=978-1-85233-617-2|page=209|edition=2nd}}</ref>, operates on composite numbers, and it is based on decomposing the number into its prime components.

The second extension, called EBR (Extended Bit-Reversal)<ref>{{cite journal|last1=Gordon|first1=Dan|title=A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates|journal=Numerical Algorithms|volume=77|issue=4|pages=1141–1157|date=June 2017|doi=10.1007/s11075-017-0356-3}}</ref>, is similar in spirit to bit-reversal. Given an array of size ''n'', EBR fills the array with a permutation of the numbers in the range <math>0\ldots n-1</math> in linear time. Successive numbers are separated in the permutation by at least <math>\lfloor n/4\rfloor</math> positions.

==Applications==

Line 46:

| doi = 10.1145/800057.808719

| pages = 493–503

| title = [[Symposium on Theory of Computing|Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84)]]

| contribution-url = http://groups.csail.mit.edu/tds/papers/Lynch/stoc84.pdf

| year = 1984}}.</ref>| title-link = Symposium on Theory of Computing

| isbn = 978-0897911337

}}.</ref>

The [[Van der Corput sequence]], a [[low-discrepancy sequence]] of numbers in the [[unit interval]], is formed by reinterpreting the indexes of the bit-reversal permutation as the [[Fixed-point arithmetic|fixed-point binary representations]] of [[dyadic rational number]]s.

Line 62 ⟶ 64:

| title = Bit reversal on uniprocessors

| volume = 38

| year = 1996| urlciteseerx = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.2913&rep=rep1&type=pdf

}}. Karp surveys and compares 30 different algorithms for bit reversal, developed between 1965 and the 1996 publication of his survey.</ref>

Line 75 ⟶ 77:

| year = 1990}}.</ref>

Another consideration that is even more important for the performance of these algorithms is the effect of the [[memory hierarchy]] on running time. Because of this effect, more sophisticated algorithms that consider the block structure of memory can be faster than this naive scan.<ref name="karp"/><ref name="cg98">{{citation|last1=Carter|first1=Larry|first2=Kang Su|last2=Gatlin|contribution=Towards an optimal bit-reversal permutation program|title=[[Symposium on Foundations of Computer Science|Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS)]]|pages=544–553|year=1998|doi=10.1109/SFCS.1998.743505|title-link=Symposium on Foundations of Computer Science|isbn=978-0-8186-9172-0|citeseerx=10.1.1.46.9319}}.</ref> An alternative to these techniques is special computer hardware that allows memory to be accessed both in normal and in bit-reversed order.<ref>{{citation

| last1 = Harley | first1 = T. R.

| last2 = Maheshwaramurthy | first2 = G. P.