Talk:Random number generator

From NESdev Wiki
Jump to navigationJump to search

Explaining edit for simplification and "advanced" page

Just to explain this edit I made, and why I created Random number generator/Linear feedback shift register (advanced). When I made this example, my goal was to make the simplest working PRNG of reasonable quality. Easy to read and understand, and good enough for practical use. It's also very simple to modify once you understand it (but not before!).

We could discuss various potential tricks, optimizations and other properties of the implementation for days and days (and we literally have, if you read the forum threads), but it's detrimental to the goal of it being a simple, clear, ready-to-use example. I was already on the fence about having an explanation of the iteration counter, but when tepples doubled its description I realized this was a mistake to include, which is why I removed it entirely.

Instead I've created the advanced LFSR page where you can feel free to annotate and ad nauseam. I think this covers the information that tepples was trying to add, as well as a number of other things I intentionally left out (like what it would look like as a 24 or 32 bit LFSR). I hope this is an acceptable solution. What I really don't want to see is a hundred tiny edits slowly overcomplicating the example. Sure, maybe it's what real production code tends to look like after it's been worked on for a long time by many people, but it isn't a good thing to learn from. - Rainwarrior (talk) 15:12, 11 July 2016 (MDT)

Good call. --Tepples (talk) 17:41, 11 July 2016 (MDT)

Other random number generators

Other pseudo random number generator algorithms exist. One is ARCFOUR; for most computer games it is probably good enough. Although, it requires 258 bytes of RAM. Regardless of what algorithm you use, if repeatability is not required you can use additional sources of entropy (such as microphone and uninitialized RAM); but do not rely on additional sources of entropy. The other thing is if you need numbers or probabilities in a range that isn't a power of 2. Assuming the random number generator provided generates uniform bits, there are ways to do this; for example if you need a 1 in 3 chance it can be like the Pokemon card "Digger" (starting with you, players take turns tossing a coin until someone gets tails, and whoever gets tails damages their own active pokemon card by 1 point) (I have calculated the probabilities of this card at 2/3 of the user damaging his own active pokemon card). --Zzo38 (talk) 11:33, 8 October 2016 (MDT)

For a 1 in 3 chance, you can compare the 8-bit result of a "typical" RNG with a uniformly distributed 8-bit result to round(256/3) = 85. Another non-power-of-two postprocessing that I've done with an RNG in several productions (Thwaite, RHDE, robotfindskitten, etc.) is a least-recently-used queue: select an index from 0 to a power of two minus one into the start of a non-power-of-two array, rotate the item there to the back, and rotate all other items one step forward. LRU is like RC4 in principle, just more specialized toward generating random game events. --Tepples (talk) 18:03, 8 October 2016 (MDT)