3 ms·
If you realize that any RNG on [0,256) always has a cycle of at most 256, this is actually pretty decent.
by xiaq 11y ago
If you realize that any RNG on [0,256) always has a cycle of at most 256, this is actually pretty decent.
- eterm 11y agoIs that true? Imagine I want to sample [0,2), then I can use the following table: [0,0,0,1,1,0,1,1]. This has cycle length 8. Much longer cycles can be obtained, it just requires the state of the prng to be larger than range being sampled.
- deathanatos 11y ago> Is that true? It is not, at least not the way you (and me) are interpreting it. A RNG's period is bounded by the number of states it has, internally[1]: > The period is bounded by the number of the states > If a PRNG's internal state contains n bits, its period can be no longer than 2 ^ n results, and may be much shorter. Our state in the Doom generator is the variable rndindex (or prndindex; we have two generators here); rndindex holds an index in [0, 256) (it is 8 bits), hence we have at most that many states (2 ^ 8, or 256). (I'm assuming the table does not repeat itself, as that would be silly, so in this case, the period is exactly 256 outputs long.) [1]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Periodicity https://en.wikipedia.org/wiki/Pseudorandom_number_generator#...
- xiaq 11y agoThanks for pointing this out. I have confused the size of output with the size of state.