News for hackers. Stuff that matters.
Re:Random in the wild by colmmacc on Tuesday December 09, 2014 @03:28PM (#8725486)
My own favourite random() in the wild bug is one that I've come across many many times:

    /* Generate a random number 0...5 inclusive */
    int r = random() % 6;  
The problem is that this results in a bias towards certain values, because the random() return space is probably not a whole multiple of the number you are modding. It's easier if you think what would happen if RAND_MAX were "10". Then the results 0,1,2,3,4 each have two opportunities of being selected for r, but "5" only has one. So 5 is half as likely as any other number. Terrible!

Using float/double random()'s don't always help either, because floating point multiplication has non-uniform errors. Instead, what you really need is:

   int random_n(int top) {
       if (top <= 0) {
            return -1;
       }
    
       while(1) {
           int r = random(top);
           if (r < (RAND_MAX - (RAND_MAX % top))) {
                return r;
           }
       }
     
       return -1;   
    }
Although it's better to replace random() itself with something that uses real entropy.
Re:Random in the wild by donmcc on Tuesday December 09, 2014 @04:41PM (#8725985)
Hence arc4random_uniform() in OpenBSD, which accounts for modulo bias (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Modulo_bi...).
Re:Random in the wild by conistonwater on Tuesday December 09, 2014 @03:38PM (#8725549)
On my machine RAND_MAX is 2^31-1. So getting the probability wrong in the way you describe means a relative error of one in two billion. That's really quite small for non-critical applications.
Re:Random in the wild by colmmacc on Tuesday December 09, 2014 @04:05PM (#8725735)
It's not so simple. The larger the modulus, the larger the error; up to a limit. If the modulus is 2^30 + 2^29 for example, then values of r in the range 0 ... 2^29 will be represented twice as often as values in the range (2^29 + 1) ... (2^30 + 2^29). This is much more significant error than one in two billion (it's close to 1 in 3, nearly ten orders of magnitude more significant).

Subtleties like this are hard to detect on code review, and even in testing ... the real lesson may be that the very interface behind random(void) is just broken. It really should be random(int) and take care of all of this for you, as many other languages/libraries do.

Re:Random in the wild by conistonwater on Tuesday December 09, 2014 @04:38PM (#8725962)
Yes, you are right, I didn't think of really large moduluses of magnitude comparable to RAND_MAX.
Re:Random in the wild by clarry on Tuesday December 09, 2014 @03:46PM (#8725599)
Doesn't matter what your RAND_MAX is if you're taking the result modulo anything that's not a power of two.
Re:Random in the wild by conistonwater on Tuesday December 09, 2014 @03:57PM (#8725675)
No, it does matter. If RAND_MAX is really large, the relative error in "incorrect" probabilities is really small. Unless you have a critical need for it to be precisely correct, the error is basically negligible.
Re:Random in the wild by clarry on Wednesday December 10, 2014 @07:46AM (#8728862)
I have no idea what I was thinking, but I stand corrected. Thanks.
Re:Random in the wild by christianmann on Wednesday December 10, 2014 @02:22AM (#8728071)
And if you have a need for it to be precisely correct, I have bad news for you about the word "random".