Content deleted Content added
→Applications: −sp |
|||
| (13 intermediate revisions by 8 users not shown) | |||
Line 30:
==Generalizations==
The generalization to [[radix]] <math>b</math> representations, for <math>b > 2</math>, and to <math>n=b^k</math>, is a '''digit-reversal permutation''', in which the base-<math>b</math> digits of the index of each element are reversed to obtain the permuted index. The same idea can also been generalized to [[mixed radix]] number systems. In such cases, the digit-reversal permutation should simultaneously
| last = Elster | first = Anne C.
| contribution = Fast bit-reversal algorithms
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
| arxiv = 1204.1958
}}.</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 ''
The second extension, called EBR (
==Applications==
Line 69 ⟶ 72:
| year = 1984| title-link = Symposium on Theory of Computing
| isbn = 978-0897911337
| doi-access = free
}}.</ref>
Line 77 ⟶ 81:
| 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 105 ⟶ 109:
| 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 116 ⟶ 121:
| title = Address generators for mapping arrays in bit-reversed order
| volume = 52
| year = 2004
| s2cid = 10043478
}}.</ref>
Significant attention has been given to improving the performance of bit-reversal operations within the field of high-performance computing. Developing architecture-aware algorithms is crucial for enabling optimal use of hardware and system software resources such as caches, TLBs, and multicore processors.<ref>{{citation
| last1 = Zhang | first1 = Zhao
| last2 = Zhang | first2 = Xiaodong
| doi = 10.1137/S1064827599359709
| issue = 6
| journal = SIAM Journal on Scientific Computing
| mr = 1856305
| pages = 2113–2134
| title = Fast bit-reversals on uniprocessors and shared-memory multiprocessors
| volume = 22
| year = 2000}}</ref>
==References==
| |||