"Splitmixes" Pseudorandom Permuter, aka "WS-APHF"

Revision en1, by Spheniscine, 2020-10-27 13:37:08

Forgive the quirkiness of the title; I am not aware of a name for this concept, therefore I just made a few up.

This blogpost is about a particular way to construct what I call a "pseudorandom permuter". It is distinct from a regular pseudorandom number generator (PRNG) in that it is constructed such that the sequence will never repeat until all $$$M = 2^k$$$ integers in its machine-integer state space (32- or 64-bit) has been used. In other words, it's a way to produce a permutation of $$$[0, M)$$$ that's (hopefully) statistically indistinguishable from a truly random permutation.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Spheniscine 2020-10-30 14:46:33 17 Tiny change: 'e blogpost](https://' -> 'e blogpost by Chris Wellons](https://'
en8 English Spheniscine 2020-10-27 14:51:18 2 Tiny change: ', \gamma}(i))$, where' -> ', \gamma}(x))$, where'
en7 English Spheniscine 2020-10-27 14:39:43 5 Tiny change: 't exhibit an avalanche' -> 't exhibit the avalanche'
en6 English Spheniscine 2020-10-27 14:28:05 1 Tiny change: 'ation of a unpredict' -> 'ation of an unpredict'
en5 English Spheniscine 2020-10-27 14:27:27 1023 Tiny change: 'oses.)\n\n' -> 'oses.)\n\n## Applications' (published)
en4 English Spheniscine 2020-10-27 14:10:01 584
en3 English Spheniscine 2020-10-27 14:04:10 1597
en2 English Spheniscine 2020-10-27 13:45:25 548 Tiny change: 'equence is:\n\n$W_{s, \ga' -> 'equence is $W_{s, \ga'
en1 English Spheniscine 2020-10-27 13:37:08 636 Initial revision (saved to drafts)