Hacker News Reader

Comment by cjackson | Hacker News Reader

Using modulo would actually bias the results making things slightly less random.

Not so. If the last digit on the clock is random, then the result is also.

     n  n % 4
    ----------- 	
     0  0
     1  1
     2  2
     3  3
     4  0
     5  1
     6  2
     7  3
     8  0
     9  1
    10  2
    11  3
    12  0
    13  1
    14  2
    15  3

EDIT: It must be really, really satisfying to be able to anonymously downvote posts that actually reveal such things as grade-school arithmetic -- thus contributing to the intellectual wasteland that most accurately represents America in the early 21st century.

you're getting upset because you're making a terminology error, you say "digit" but mean "digits". A digit is either a finger, or the numbers 0-9, singular.

I'm getting outraged by the number of brainless cyberlawyers who think downvoting a post constitutes a creative act, on a par with knowing something about the topic of discussion.

The pattern is clear and ubiquitous -- if you actually know something, and if you're foolish enough to post a clear exposition, the morons who never post anything coherent will downvote your posts with a probability approaching certainty.

The modulo operator is the obvious solution to the original question. And if there were't an atmosphere of pervasive anti-intellectualism at HN, this thread would be much shorted than it is.

Well, you are incorrect. The simple use of modulo does result in a bias. See for instance, modulo 7:

From this, you can clearly see that:

    0 appears nine times.
    1 appears nine times.
    2 appears nine times.
    3 appears nine times.
    4 appears *eight* times.
    5 appears *eight* times.
    6 appears *eight* times.

This is not fair, and is an actual problem in real life: Two examples off the top of my head is when drawing cards in electronic poker games (where slight biases in the PRNG can be exploited by those who notice them) and in cryptography.

> Well, you are incorrect. The simple use of modulo does result in a bias.

You're arguing against something I never said. Large numbers reduce the bias, they don't eliminate it. Notice that earlier I considered the objection of a hypothetical clever child by using the minute digits as well. All these steps only minimize the bias in favor of small numbers, that cannot be eliminated. Even a 64-bit random number possesses this property. And the classic remedy for this bias is to apply the modulo operator to get the desired range.

And the classic remedy for eliminating bias is to redraw/reshuffle if the number is outside of the desired range. Note, this completely eliminates all bias. The negative aspect is that in this case, random number generation can take arbitrarily long (with rapidly diminishing probabilities); 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).

You've failed to acknowledge the trade-offs of using your solution versus the OP's solution (or the solution above), and you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.

> 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.

You'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?

Even worse - non-coprime with the entropy source. That's why I had to change the example to 6 children.

> versus the OP's solution (or the solution above)

Would that solution be "multiply by the number of children and divide by ten"? Let's see:

     n  n * 7 / 10
    ---------------
     0  0
     1  0
     2  1
     3  2
     4  2
     5  3
     6  4
     7  4
     8  5
     9  6

Not a very desirable distribution. But then, the OP could have established this fact before posting.

> ... you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.

No, I am being downvoted because I'm right. Being right is simply rude, but being right about something trivially proven is beyond the pale.

>Would that solution be "multiply by the number of children and divide by ten"

No; his/her solution is: If 0-9 couldn't be divided evenly among the kids present, leftover digits would result in a re-roll, exactly as I said above.

> No, I am being downvoted because I'm right

Are you? This is math we're talking about, right and wrong are very precisely defined. For the sake of discussion, can you repeat the question you claim to have the right/correct solution to, and your answer?

Reply on news.ycombinator.com