[core] Uniform Random Generators are not Uniform

[orcmid]

---

Please, before submitting a new issue verify and check:

• I tested it on latest raylib version from master branch
• I checked there is no similar issue already reported
• I checked the documentation on the wiki
• My code has no errors or misuse of raylib

Issue description

In rcore.c when SUPPORT_RPRAND_GENERATOR is not defined, the supplied code for computing uniform random values in GetRandomValue(min, max) and LoadRandomSequence(count, min, max) does not provide uniformly random results.

That is because

value = (rand()%(abs(max - min) + 1) + min)

will not be uniform even though rand() is. According to Knuth, the bias is small when abs(max-min) is small, but the larger it is, the greater is the bias. I am looking at Knuth's explanation and solution in The Stanford GraphBase Code for GB_FLIP section 12. Uniform Integers.

Also, since GetRandomValue(min, max) already interchanges the values so that max > min, the abs(max-min) is unnecessary. The cautions about overflowing either INT_MAX and RAND_MAX remain important.

Environment

This applies to all platforms where rand() is supplied by the C Language <stdlib.h>.

Issue Screenshot

The issue is visible in the code of rcore.c.

Code Example

I am not going to the effort to demonstrate the bias. It occurs when RANDMAX is not a multiple of max-min+1, so some remainders occur more than others.

Proposed Solution

First, LoadRandomSequence should use GetRandomValue(min, max) and that will also protect against deviant parameter cases.
If that is undesirable, unwind the key part of updated GetRandomValue(min, max) there.

Secondly, in GetRandomValue(int min, int max), replace the line

value = (rand()%(abs(max - min) + 1) + min;

with the following code

const long m = (long) max - (long) min + 1;    // # values in range 0 to m-1
const long c = (long) RAND_MAX+1;               // # values in range 0 to RAND_MAX
const long t = c - c % m;                                  // largest multiple of m not greater than c
long r;

do r = (long) rand();
     while (t <= r)                                               //  reject r's not inside the uniform t box
value = min + (int)(r % m);

I have not tested this code. I have probably failed the raylib code-formatting requirements.
This is, by the way, demonstration of when do ... while is perfect.

KEY POINTS: The use of long is to deal with cases where RAND_MAX is INT_MAX. An useful case to desk-check is with min = 0 and max = RAND_MAX. It will just fall through. This code will fail if m (that is, max-min+1) is greater than RAND_MAX, even if max - min +1 does not overflow. The precautions at the beginning of GetRandomValue are important.