Bit-reversal permutation: Difference between revisions

Content deleted Content added
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
m Reverted edit by Mepperelf (talk) to last version by Joe in Australia
 
(5 intermediate revisions by 5 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 reversesreverse the digits of each item and the bases of the number system, so that each reversed digit remains within the range defined by its base.<ref>{{citation
| last = Elster | first = Anne C.
| contribution = Fast bit-reversal algorithms
Line 52:
| volume = 113
| year = 2013| s2cid = 14672841
| arxiv = 1204.1958
}}.</ref>
 
Line 120 ⟶ 121:
| title = Address generators for mapping arrays in bit-reversed order
| volume = 52
| year = 2004| s2cidbibcode = 100434782004ITSP...52.1693H
| s2cid = 10043478
}}.</ref>
 
TheSignificant performanceattention improvementhas ofbeen bit-reversalsgiven into bothimproving uniprocessorthe andperformance multiprocessorsof hasbit-reversal beenoperations paidwithin athe seriousfield attention inof high-performance computing fields. BecauseDeveloping architecture-aware algorithmalgorithms developmentis cancrucial bestfor utilizeenabling optimal use of hardware and system software resources, includingsuch as caches, TLBTLBs, and multicores, significantly accelerating themulticore computationprocessors.<ref>{{citation
| last1 = Zhang | first1 = Zhao
| last2 = Zhang | first2 = Xiaodong