For clarity, this worst case for this approach should happen for ranges with size 2*x+1, ie one more than a power of two.
The bug is known but not being fixed right now to keep random number output consistent.
That brings back an old (> 3 decades) memory… Way back when, not actually part of a homework assignment but a time in my life I would get them, I noticed a bias while picking random cards. This IIRC was with a 16 (or maybe even 8) bit PRNG, I'm not sure if the significance of the bias was due to that or just if the PRNG overall was terrible. After doing some simple analysis to prove some cards were less likely to be picked, my answer was to actually shuffle the deck: move the cards around in an array, looping over the whole array picking a new position for each card, multiple times. Of course it was slow so would not fit in with the "efficient" goal of this article, but it did seem to smooth out the bias, and picking in order from a pre shuffled deck much better emulated the real world game I was trying to implement at the time (so why wasn't I doing that from the offset?: the bad design process of a early-teens self-taught fledgeling programmer!).
The analysis (written almost entirely in BASIC though the shuffle was in 6502 assembly as I was learning that a bit at the time) was my first experience of running a programmed process over several hours, my parents were dubious about the good ol' BBC Master needing to be left powered on all night! The results may have been completely wrong but (very) young me was convinced at the time. Ahh, innocent times…
Somewhere in my github there's an indefinite-width multiply that only adds bits while there's a risk of carry into the 1's digit; the check for that is quite cheap.
I wonder what is the best real-time (fixed latency) approach for unbiased ranges?
cbarrick•6mo ago