Content deleted Content added
No edit summary Tags: Reverted Visual edit |
m Reverted edits by Lasantha.Adikaram (talk) to last version by WikiCleanerBot |
||
Line 1:
In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of ''n'' items, where ''n'' = 2<sup>''k''</sup> is a [[power of two]]. It is defined by indexing the elements of the sequence by the numbers from 0 to ''n'' − 1 and then reversing the [[binary representation]]s of each of these numbers (padded so that each of these binary numbers has length exactly ''k''). Each item is then mapped to the new position given by this reversed value. The bit reversal permutation is an [[Involution (mathematics)|involution]], so repeating the same permutation twice returns to the original ordering on the items
This permutation can be applied to any sequence in [[linear time]] while performing only simple index calculations. It has applications in the generation of [[low-discrepancy sequence]]s and in the evaluation of [[fast Fourier transform]]s.
Line 68:
==Algorithms==
Mainly because of the importance of [[fast Fourier transform]] algorithms, numerous efficient algorithms for applying a bit-reversal permutation to a sequence have been devised.
| last = Karp | first = Alan H.
| doi = 10.1137/1038001
Line 90:
| 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.
| last1 = Harley | first1 = T. R.
| last2 = Maheshwaramurthy | first2 = G. P.
| |||