jeudi 1 août 2019

Efficiently randomly shuffling the bits of a sequence of words

Consider the following algorithm from the C++ standard library: std::shuffle that has the following signature:

template <class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g);

It reorders the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.


I am trying to implement the same algorithms, but which works at the bit level, randomly shuffling the bits of the words of the input sequence. Considering a sequence of 64-bits words, I am trying to implement:

template <class URBG>
void bit_shuffle(std::uint64_t* first, std::uint64_t* last, URBG&& g)


Question: How to do that as efficiently as possible (using compiler intrinsics if necessary)? I am not necessarily looking for an entire implementation, but more for suggestions/directions of research, because it's really not clear to me if it's even feasible to implement that efficiently.




Aucun commentaire:

Enregistrer un commentaire