4 ms·

You probably have something like 2^32 ways to seed your RNG. But there are N! possible outcomes of the shuffle, so at most 2^32 of those will appear (one per s

by jrp 17y ago

You probably have something like 2^32 ways to seed your RNG. But there are N! possible outcomes of the shuffle, so at most 2^32 of those will appear (one per seed). 2^32 = 4294967296 100! is about 10^158 So for just 100 items, you're already missing most of your outcome space. You might switch to a generator with a bigger seed. For this example with 100 items, you need at least log(100 !) / log(2) = 524.764993 bits in your seed. For N items to be sorted, you need about NlogN bits in your seed. So if you're trying to actually make each outcome possible, then no matter which clever algorithm you use to go from random numbers to a shuffled sequence, you've already lost.

allenbrunson 17y ago
hrm. never thought of it that way before. but assuming I seed the prng only once at the beginning of a program run, i could hit every possible shuffle on subsequent deals, couldn't I?
- fhars 17y ago
  No, you couldn't, that's what this subthread is about. A PRNG with 32 bit entropy will only ever produce 2^32 different sequences of random numbers and so only 2^32 different shuffles. If you want more, you must introduce more entropy, either by using a larger PRNG, or using a hardware RNG. Calling the same PRNG fro diffferent threads (don't forget your synchronization primitives!) might also work as a cheap source of entropy but will likely have either bad statistical properties or horrible performance: for it to make a real difference, every single shuffle of a deck must be interspersed with many calls to the PRNG from other threads. If calls from other threads do only happen between shuffles, all you gain from introducing shared state concurrency into your program is that the same 2^32 permutations are generated in a different order. But, as I remarked earlier, if this is just for a game that is for fun where opponents can't cheat you or other players out of large amounts of money by predicting which permutations may or may not occurr, you may get away with whatever PRNG you have at hand and only swap is out once many players start to complain that they had this very hand one or two billon games ago.

by jrp 17y ago

allenbrunson 17y ago

hrm. never thought of it that way before. but assuming I seed the prng only once at the beginning of a program run, i could hit every possible shuffle on subsequent deals, couldn't I?

fhars 17y ago
No, you couldn't, that's what this subthread is about. A PRNG with 32 bit entropy will only ever produce 2^32 different sequences of random numbers and so only 2^32 different shuffles. If you want more, you must introduce more entropy, either by using a larger PRNG, or using a hardware RNG. Calling the same PRNG fro diffferent threads (don't forget your synchronization primitives!) might also work as a cheap source of entropy but will likely have either bad statistical properties or horrible performance: for it to make a real difference, every single shuffle of a deck must be interspersed with many calls to the PRNG from other threads. If calls from other threads do only happen between shuffles, all you gain from introducing shared state concurrency into your program is that the same 2^32 permutations are generated in a different order. But, as I remarked earlier, if this is just for a game that is for fun where opponents can't cheat you or other players out of large amounts of money by predicting which permutations may or may not occurr, you may get away with whatever PRNG you have at hand and only swap is out once many players start to complain that they had this very hand one or two billon games ago.