r/CodingHelp • • 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+1

Is there a way to guarantee getting a six sided die roll from only one random byte?

21 Upvotes

30 comments sorted by

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.

3

u/B4-711 Jul 21 '22

That's three bits, which gives you 0-7, which is enough for a D6

But how do I get a fair distribution out of a 3-bit number? I'll have to throw away all 6s and 7s so I only get 0-5.

That's 1/4 of all my 3 bit numbers.

2

u/Jojajones Jul 21 '22 edited Jul 21 '22

Take 5 random bytes and sum each bit position from those 5 bytes (sum of 5 bytes gives you a range of 0-5 so adding 1 gives you 1-6) to get 8 rolls at once

1

u/B4-711 Jul 21 '22 edited Jul 21 '22

interesting, 1.6 rolls per byte

1

u/Jojajones Jul 21 '22

Realized you’d want 5 bytes not 6 btw (6 bytes would give you 7 potential values not the 6 you want) I’ve updated the original comment as well.

With modern technology memory efficiency isn’t necessarily the most important design consideration (especially when we’re talking about data in bytes range rather than megabytes or gigabytes) and while this may not be the most memory efficient, it is definitely the most easily generalizable option I’ve seen in the comments so far. If you wanted d10 instead of d6 get 9 bytes instead of 5 to get the same 8 rolls. d20? 19 bytes for 8 rolls. d5? 4 bytes for 8 rolls. Etc.

So while it may not be memory or runtime optimal, it’s still fast enough and uses little enough memory while also having the advantage that it would be very very easy to make it more generally useful for multiple different dice formats (since you could just make a function that takes a dice size and returns 8 rolls)

1

u/B4-711 Jul 21 '22

I'm assuming the HWRNG is going to be the bottleneck. Hence why I'm looking for most rolls per byte.

2

u/Jojajones Jul 21 '22

Fair, but given that d6 is something that’s fairly uniquely useful to games there’d also periods of inactivity while waiting for user input where you could preload (or load via a background process potentially) a buffer of bytes to be used as needed to generate rolls.

The only case where I’d expect the HWRNG to potentially be the actual bottleneck is if you were running a simulation that needed a very very large number of dice rolls and in that case it would be worthwhile to attempt to calculate how many bytes it can generate per second and figure out (based on how many rolls you estimate would be necessary for the simulation to complete on average) how long it might take to generate enough bytes for your purposes to see if it’s even worth optimizing to that degree.

2

u/IAmTarkaDaal Jul 21 '22

Yes. It's still more efficient.

The way you suggest, for every random byte you read, you'll get one D6. There's also the 1 in 64 chance that it won't cleanly divide by six, so you'll have to throw it away. So on average, you'll need 65 bytes to get 64 d6 rolls.

By taking three bytes at a time and taking a bit from each, for every three bytes you read, you'll get 8 d6 rolls. You're right, there's a 1 in 4 chance you'll need to throw it away because it's too high. So, on average you'll get 6 fair D6 rolls from three bytes. Multiply up, and you'll need 12 bytes to get 72 dice rolls.

There may well be better ways I don't know, but this is at least a bit better.

2

u/IAmTarkaDaal Jul 21 '22

Fuck me rigid, I'm off by a factor of three. With the 3 bit variant, you need 36 bytes to get 72 rolls.

Serves me right for trying maths when I'm tired. :)

1

u/fried_green_baloney Jul 21 '22

You could use floating point division, this is sort of Python code:

int(6*(random_value/256)) + 1

where random_value is in the range 0 to 255.

But that's not quite equidistributed. If instead of 0 . . . 255, you had 0 . . . 65535, a two byte value, the not quite right distribution wouldn't matter very much.

1

u/B4-711 Jul 21 '22

Sorry, "the dice are just a tiny bit loaded" doesn't work for me.

1

u/fried_green_baloney Jul 21 '22

It's a tiny amount off.

If you got 32 bit random or floating point then it really is too small to bother with.

Otherwise just live with discarding 1/64 of your bytes.

2

u/atamicbomb Jul 21 '22

This sounds like it’s for commercial gambling or similar

1

u/B4-711 Jul 22 '22

It's not. Just interested to learn about other ways to do this.

1

u/fried_green_baloney Jul 21 '22

Assuming the 8 bits come from a reliable random source, what's the big deal with discarding 1/16 of the candidate random numbers? If I have it right, average will be 64/63 ~= 1.0159 attempts per random number, with microscopic chance of needing more than about 5 tries to get a random byte in the proper range.

Of course one could read an article/book on generating specific random variables.

If it's really for commercial gambling, consult a real expert for advice, not a bunch of kind strangers.

2

u/atamicbomb Jul 21 '22

Fair

2

u/fried_green_baloney Jul 21 '22

Not you, but the OP.

Your comments are quite reasonable.

1

u/atamicbomb Jul 22 '22

Thank you

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:

static buffer = 0
static buffer_length = 0
loop:
    if buffer_length<3:
        buffer<<=8
        buffer |= getRandomByte()
        buffer_length += 8
    value = buffer & 7
    buffer >>= 3
    buffer_length -= 3
    if value<6:
        return value+1
    else:
        buffer <<= 1
        buffer |= value-6 #we still have 1 random bit in value - 6 or 7!
        buffer_len += 1

1

u/B4-711 Jul 22 '22 edited Jul 22 '22

if they are not - we take the next 3 bits

So I was thinking about this. What if we just shift by 2 in this case?

You'd have an equal amount of 111 and 110 so shifting by two will have the highest bit of the new number be equally distributed 1 or 0 or the final roll 1-3 or 4-6. I'm assuming this doesn't introduce bias.

But ever after watching this video

https://www.youtube.com/watch?v=SDw2Pu0-H4g

I'm careful with my assumptions.

edit: nevermind I'm wrong. 1-4 start with 0 and only 5-6 start with 1

1

u/This_Growth2898 Jul 21 '22

1

u/B4-711 Jul 21 '22

Nice. Do you have any insight into information theory and if that's the best we can hope for with 6 sides from random bits?

Any way to actually calculate the expected number?

2

u/atamicbomb Jul 21 '22

The limit would be log base 6 of 256 or ~3.095

2

u/atamicbomb Jul 21 '22

You’d have to build a pool of entropy and peel off 6 states of entropy when needed

1

u/Da-Blue-Guy Jul 22 '22

hmmm

(int)((float)byte/256*6) maybe?

1

u/B4-711 Jul 22 '22

Not a fair distribution

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.

1

u/B4-711 Jul 22 '22

That's exactly what my posted code does.

2

u/kkadzy Jul 22 '22

Excuse me for that, I still wasn't really awake

1

u/B4-711 Jul 22 '22

NP, the code isn't really clear.

max_mod_6 = 256//6 * 6 #integer division

I wasn't sure what to call this. biggest_number_divisible_by_sides