3 ms·
Four flips can get you 16 outcomes of course, rerolling values out of bounds means you need 4*16/10 = 6.4 amortized flips to generate a d10, or ~154 total to ge
by ajross 9y ago
Four flips can get you 16 outcomes of course, rerolling values out of bounds means you need 4*16/10 = 6.4 amortized flips to generate a d10, or ~154 total to get 24d10.
For large dice counts like that, it's probably better to just use a manual table for a bell curve based on ~8-10 flips. No human player is going to care about result fidelity beyond a thousand possible results anyway.
- ajross 9y agoActually 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.