An improved digit-reversal permutation algorithm (Q687353)

This paper improves the speed of the digit-reversal permutation in the radix-\(B\) fast Fourier or Hartly transform on \(N\) data, where \(N = B^ P\). Its mathematical basis is as follows: Let \(i = (0 0 \dots y_ my_{m-1}\dots y_ 1)_ B\) and \(j = (0 0\dots x_ 1x_ 2\dots x_ m)_ B\). If \(P\) is an even number, then \(B = 2^ m\), and \(0 \leq i,j \leq B^{m-1} = \sqrt{N}-1\). Thus \(k = (x_ mx_{m-1}\dots x_ 1y_ my_{m-1}\dots y_ 1)_ B = i + R[j]\). Hence \(R[k] = R[i]+j\). If \(P\) is odd, \(P = 2m+1\), and \(0 \leq i,j \leq B^ m-1 = \sqrt{N/B}-1\). Then \(k = i + R[j] + zB^ m\) with the middle digit \(z\) where \(0 \leq z \leq B-1\). Thus \(R[k] = R[i] + j + zB^ m\).