3 ms·
> to make it more efficient, you could first use a modulo operation, but only using a base that divides the original range (e.g. for 7 kids and 60 seconds, do 6
by mindslight 12y ago
> to make it more efficient, you could first use a modulo operation, but only using a base that divides the original range (e.g. for 7 kids and 60 seconds, do 60 mod 10, then redraw if the result is 7, 8 or 9).
This makes it less efficient - in this case, 18/60 chance of having to redraw, versus 4/60. Taking the modulus of the largest range you can leaves less residue (what lutusp is alluding to, without realizing others are describing a simple way of getting an exact uniform distribution).
If you want to make it more efficient (in terms of entropy used), you need to save the 1-of-prime (eg bits, trits, etc) that have been successfully chosen (uniformly). For example, with 6 children and an 8 sided die (3 bits), a roll of 6 or 7 would narrow the choices to only children 0-2 or 3-5 respectively. Your subsequent rolls could then be done with a 4 sided die.
- tomp 12y agoYou're right, I don't know what I was thinking... Anyways, about your second paragraph, doesn't that only work if the number of desired outcomes (children) is non-prime?
- mindslight 12y agoEven worse - non-coprime with the entropy source. That's why I had to change the example to 6 children.