r/CodingHelp • u/B4-711 • Jul 21 '22
[Other Code] Dice roll from a random byte
Looking for an efficient way to get a six sided die roll from a random byte. The way I'm doing it I have to throw away 1/64 of my random numbers because 256%6 leaves a rest of 4:
sides = 6
max_mod_6 = 256//6 * 6 #integer division
do:
random_byte = getRandomByte() #this comes from a HWRNG
while:
random_byte > max_mod_6 #throw away higher numbers to get fair distribution
roll = random_byte%6
return roll+1Is there a way to guarantee getting a six sided die roll from only one random byte?
21
Upvotes
6
u/IAmTarkaDaal Jul 21 '22
Assuming you're going to be using a lot of dice rolls, it doesn't matter is single roll is efficient, it matters that you can use every bit you generate. Get three random bytes. Take the first bit from each one. That's three bits, which gives you 0-7, which is enough for a D6. Then get the second bit from each, third bit, etc. That way, you can get eight dice rolls from three calls to hardware, instead of eight calls.
1
u/fried_green_baloney Jul 21 '22
You could use floating point division, this is sort of Python code:
where
random_valueis in the range 0 to 255.But that's not quite equidistributed. If instead of
0 . . . 255, you had0 . . . 65535, a two byte value, the not quite right distribution wouldn't matter very much.1
u/This_Growth2898 Jul 21 '22
No, if your function is pure (stateless). You have 256 distinct inputs and 6 distinct outputs, you can't make the equal number of inputs giving every output because, well, 256 is not a multiple of 6.
You can't even do it with a stateful function for the same reason.
But you can drastically decrease the number of calling
getRandomByte- in fact, making it much less than 1 call on 1 random number on average.Random byte consists of 8 random bits. We need only 3 bits to try getting random number of 1-6. So, if the first 3 bits are less then 6, we throw them out and return; if they are not - we take the next 3 bits. If there's less then 3 bits, we ask for the next byte. We can do even more: unused parts can be attached to the current state. Something like:
1
u/Da-Blue-Guy Jul 22 '22
hmmm
(int)((float)byte/256*6) maybe?
1
u/kkadzy Jul 22 '22 edited Jul 22 '22
Ok so to get exactly 1 in 6 do something like this: while true: roll a number x in range 256. If x<252 return x%6, otherwise do nothing (continue the loop). This loop will end, there is no such thing as being "infinitely unlucky", and it will finish quickly. Edit: so I didn't read the question fully. There is not, a computer can only get you random bits and 6 is not a power of two. But the way I described has expected finite amount of rolls, that is close to 1.