Content deleted Content added
→Algorithms: fix cite and remove copyvio commons link |
Citation bot (talk | contribs) Alter: pages, contribution-url. URLs might have been anonymized. Add: s2cid. Formatted dashes. | Use this bot. Report bugs. | #UCB_CommandLine 134/9214 |
||
Line 36:
| pages = 1099–1102
| title = IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '89, Glasgow, Scotland, May 23-26, 1989
| year = 1989
}}</ref>
Permutations that generalize the bit-reversal permutation by reversing contiguous blocks of bits within the binary representations of their indices can be used to interleave two equal-length sequences of data in-place.<ref>{{citation
Line 50 ⟶ 51:
| title = In-place permuting and perfect shuffling using involutions
| volume = 113
| year = 2013
}}.</ref>
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>{{citation|last1=Herman|first1=Gabor T.|author1-link=Gabor Herman|title=Fundamentals of Computerized Tomography|url=https://archive.org/details/fundamentalscomp00herm|url-access=limited|date=2009|publisher=Springer|___location=London|isbn=978-1-85233-617-2|page=[https://archive.org/details/fundamentalscomp00herm/page/n216 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), is similar in spirit to bit-reversal. Given an array of size <math>n</math>, 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.<ref>{{citation|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|s2cid=254889989 }}</ref>
==Applications==
Line 78 ⟶ 80:
| contribution = Lower Bounds for Accessing Binary Search Trees With Rotations
| doi = 10.1109/SFCS.1986.28
| pages =
| title = 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
| contribution-url = https://ieeexplore.ieee.org
| year = 1989| title-link = Symposium on Foundations of Computer Science
| isbn = 0-8186-0740-8
Line 106 ⟶ 108:
| title = International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90)
| volume = 3
| year = 1990| s2cid = 122373780
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=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|s2cid=14307262 }}.</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.
Line 117 ⟶ 120:
| title = Address generators for mapping arrays in bit-reversed order
| volume = 52
| year = 2004
}}.</ref>
The performance improvement of bit-reversals in both uniprocessor and multiprocessors has been paid a serious attention in high-performance computing fields. Because architecture-aware algorithm development can best utilize hardware and system software resources, including caches, TLB, and multicores, significantly accelerating the computation.<ref>{{citation
|