bitreversal

[make-github-pseudonymous-again]

It is possible to implement a bitreversal generator in O(n) time using half the space requirement of the bitreversal array constructor currently implemented.

A first idea is to call bitreversal( n ) which will generate an array of size n and then yield the different values of bitreversal( 2n ) from this list.

let sigma = bitreversalarray( n ) ;
for ( s of sigma ) yield s << 1 ;
for ( s of sigma ) yield s << 1 + 1 ;

A second idea is to go for a full generator implementation using a FIFO queue. Note that the recursion stack uses an additional O(log n) space.

let queue = new Queue( ) ;
for ( s of bitreversal( n ) ) yield queue.put( s << 1 ) ;
for ( let i = 0 ; i < n ; ++i ) yield queue.get( ) + 1 ;

Finally, it is possible to implement a bitreversal generator running in O(n log n) time and using O(log n) space.

for ( s of bitreversal( n ) ) yield s << 1 ;
for ( s of bitreversal( n ) ) yield s << 1 + 1 ;

[make-github-pseudonymous-again]

Note that it is also possible to generate all values on the fly using https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel in O(n log log n) and O(1) space.

for ( let i = 0 ; i < n ; ++i ) yield reverse( i ) ;