2 ms·
A fun read. Does anyone know of a practical use for a very fast, parallelizable shuffle algorithm that uses few random bits? All the shuffling I've done has u
by dripton 11y ago
A fun read.
Does anyone know of a practical use for a very fast, parallelizable shuffle algorithm that uses few random bits? All the shuffling I've done has used small enough N that Fisher-Yates was just fine.
- darkmighty 11y agoNote the minimum number of bits is ceil(n*log2(n)). This seems to achieve nlog2(n)+O(n).
- teraflop 11y agoTechnically, the lower bound is log2(n!), which is slightly less than n * log2(n). According to the table of experimental results, the algorithm described in this paper and two of its competitors can all do better than n * log2(n) bits.
- darkmighty 11y agoAh yes log2(n!) is O(n.log2(n)) bits, not actually n.log2(n) bits. From Stirling's approximation* it seems it's more like n.log2(n)-n+O(log2(n)) bits. https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation
- im3w1l 11y agoI thought Fisher-Yates used the minimum amount of randomness possible?
- ctchocula 11y agoI think using a parallelizable random permutation is useful in parallel versions of certain graph algorithms such as maximal independent set. [1] [1] https://www.cs.cmu.edu/~jshun/mis.pdf https://www.cs.cmu.edu/~jshun/mis.pdf