3 ms·
Actually I'm realizing a much more efficient (but still simple enough to be practical) way to generate d10 results is to do them in pairs. Do seven flips to ge
by ajross 9y ago
Actually I'm realizing a much more efficient (but still simple enough to be practical) way to generate d10 results is to do them in pairs. Do seven flips to generate a binary number to be interpreted as a "percentile" result in the range 00-99, rerolling on 100-127, then treat the two digits independently.
That gets you to 4.48 amortized flips per d10.
- zaroth 9y agoNow if you just had a bit more time on your hands to work on this problem...
- nybble41 9y agoWhy stop there? If you switch to triples (10 flips, reroll on 1000-1023) then you can get an amortized cost of about 3.4 flips per d10. That's very close to the ideal outcome of log2(10) ~= 3.32 flips. Above 3d10 the rate of re-rolls increases; 20 flips for 6d10 gives a worse amortized cost than two sets of three.