Bit-reversal permutation: Difference between revisions

Content deleted Content added
Algorithms: Clean up/copyedit
m changed common redundancy "separate out" to just be "separate"
Tag: Reverted
Line 110:
| volume = 3
| year = 1990| s2cid = 122373780
}}.</ref> Because bit-reversal permutations may be repeated multiple times as part of a calculation, it may be helpful to separate out the steps of the algorithm that calculate index data used to represent the permutation (for instance, by using the doubling and concatenation method) from the steps that use the results of this calculation to permute the data (for instance, by scanning the data indexes in order and performing a swap whenever the swapped ___location is greater than the current index, or by using more sophisticated [[Vectored I/O|vector scatter–gather operations]]).<ref name="karp"/>
 
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