[math-fun] Philox random number generator. Not as smart as they think.
In that "best paper award" paper, John K. Salmon, Mark A. Moraes, Ron O. Dror, and David E. Shaw: Parallel Random Numbers: As Easy as 1, 2, 3 http://www.thesalmons.org/john/random123/papers/random123sc11.pdf they recommend random number generators based on 1) increment a counter 2) encrypt the counter via multiple rounds of "philox" transformations. A philox transform (which is a bijection) inputs two w-bit machine words L and R and outputs L' and R' where L' = R*M mod 2^w R' = floor(R*M / 2^w) XOR L XOR K where M is an odd constant and K is a constant (M and K can vary in different philoxes and they choose their Ms and Ks via a search for good ones that cause high "avalanching"). If we have a 64-bit machine and use L1,R1,L2,R2 for 256 bits in all in 4 words, then philox(L1,R1); //uses M1 which is fixed and K1 which increments by a constant philox(L2,R2); //uses M2 which is fixed and K2 which increments by a constant swap(R1,R2); is a "round". They find 7 rounds suffices to get immunity to the "crush U01" randomness test suite. One nice feature is you can tell it to use more rounds for less speed but more randomness (tunable). They also have other PRNGs based on the threefish and AES ciphers, but they are much more complicated to describe. CRITICISMS: Unfortunately, the flow of information in a philox transformation exhibits unidirectionality from the least- toward the most-significant bits. That is: Hi bits of R cannot affect lo bits of L'. Hi bits of L cannot affect lo bits of R'. Bits of L cannot affect any bits in L'. Therefore, the least-signif bits of L and R are going to be "less random" than its most-sig bits. Fortunately hi bits of R can affect lo bits of R' preventing complete death, but this gets the job done too slowly: it pathetically takes 3 rounds for hi bits of L to affect lo bits of (the new) L! To address this stupid deficiency, one might therefore consider interspersing philox transforms with these other kind of bijective transform: R = R XOR shiftright(R, H); and/or L = L XOR shiftright(L, H); and/or R = R XOR shiftright(L, H); where the H are (possibly varying) constants between 0.4 and 0.9 times the wordsize in bits. Furthermore to take advantage of multiply-and-accumulate when your computer has it, I'd recommend slightly redefining philox as L' = R*M mod 2^w R' = (floor(R*M / 2^w) + K mod 2^w) XOR L which is still a bijection. Furthermore, the idea of "increment a counter" is a bit too extreme (it leaves hi order bits almost always the same); we instead could increment one word by any odd constant (not 1) and increment a second word by a different odd constant (except not when the first word happens to equal 0). Something like this still has the same period as a counter but it changes a lot more bits every whack. Given that, you might want to dispense with K. AND SO.... My "better than best paper" award please? :)
Hi Warren, the paper doesn't give the details of the "Threefish N-word P-box" transformation, but it's more complicated than swap(R1,R2) for exactly the reasons you mention (better mixing of low and high bits). A single 4-word philox round actually looks like this: (L1, R1, L2, R2) => (low(R2*M2), high(R2*M2) xor L1 xor K2, low(R1*M1), high(R1*M1) xor L2 xor K1) Changing some of the "xors" to adds to shave a cycle using madd instructions is a good idea. Also, you can indeed get rid of K altogether and still pass BigCrush with 7 rounds; the key was included just to show how one could be introduced if desired. Incrementing a counter really is just fine; it doesn't matter that the high bits are the same. In fact, any single-bit mutation of the input produces a statistically uncorrelated output (that is, there is no correlation that BigCrush is able to detect), so you don't get any additional advantage from more complicated counter schemes. J.P. On Thu, Feb 2, 2012 at 9:08 PM, Warren Smith <warren.wds@gmail.com> wrote:
In that "best paper award" paper, John K. Salmon, Mark A. Moraes, Ron O. Dror, and David E. Shaw: Parallel Random Numbers: As Easy as 1, 2, 3 http://www.thesalmons.org/john/random123/papers/random123sc11.pdf they recommend random number generators based on 1) increment a counter 2) encrypt the counter via multiple rounds of "philox" transformations.
A philox transform (which is a bijection) inputs two w-bit machine words L and R and outputs L' and R' where L' = R*M mod 2^w R' = floor(R*M / 2^w) XOR L XOR K where M is an odd constant and K is a constant (M and K can vary in different philoxes and they choose their Ms and Ks via a search for good ones that cause high "avalanching").
If we have a 64-bit machine and use L1,R1,L2,R2 for 256 bits in all in 4 words, then philox(L1,R1); //uses M1 which is fixed and K1 which increments by a constant philox(L2,R2); //uses M2 which is fixed and K2 which increments by a constant swap(R1,R2); is a "round". They find 7 rounds suffices to get immunity to the "crush U01" randomness test suite. One nice feature is you can tell it to use more rounds for less speed but more randomness (tunable).
They also have other PRNGs based on the threefish and AES ciphers, but they are much more complicated to describe.
CRITICISMS: Unfortunately, the flow of information in a philox transformation exhibits unidirectionality from the least- toward the most-significant bits. That is: Hi bits of R cannot affect lo bits of L'. Hi bits of L cannot affect lo bits of R'. Bits of L cannot affect any bits in L'. Therefore, the least-signif bits of L and R are going to be "less random" than its most-sig bits. Fortunately hi bits of R can affect lo bits of R' preventing complete death, but this gets the job done too slowly: it pathetically takes 3 rounds for hi bits of L to affect lo bits of (the new) L! To address this stupid deficiency, one might therefore consider interspersing philox transforms with these other kind of bijective transform: R = R XOR shiftright(R, H); and/or L = L XOR shiftright(L, H); and/or R = R XOR shiftright(L, H); where the H are (possibly varying) constants between 0.4 and 0.9 times the wordsize in bits.
Furthermore to take advantage of multiply-and-accumulate when your computer has it, I'd recommend slightly redefining philox as L' = R*M mod 2^w R' = (floor(R*M / 2^w) + K mod 2^w) XOR L which is still a bijection.
Furthermore, the idea of "increment a counter" is a bit too extreme (it leaves hi order bits almost always the same); we instead could increment one word by any odd constant (not 1) and increment a second word by a different odd constant (except not when the first word happens to equal 0). Something like this still has the same period as a counter but it changes a lot more bits every whack. Given that, you might want to dispense with K.
AND SO.... My "better than best paper" award please? :)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
J.P. Grossman -
Warren Smith