lundi 6 août 2018

Java: Over-represented candidates in random number generator?

Here is a method to generate long-type random number in the StdRandom class of "Java Algorithms and Clients - Algorithms, 4th Edition".

    public static long uniform(long n) {
    if (n <= 0L) throw new IllegalArgumentException("argument must be positive: " + n);

    // https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#longs-long-long-long-
    long r = random.nextLong();
    long m = n - 1;

    // power of two
    if ((n & m) == 0L) {
        return r & m;
    }

    // reject over-represented candidates
    long u = r >>> 1;
    while (u + m - (r = u % n) < 0L) {
        u = random.nextLong() >>> 1;
    }
    return r;
}

Can anyone explain what the (u + m - (r = u % n) < 0L) part is doing? I can't understand what does it mean by "over-represented candidates".




Aucun commentaire:

Enregistrer un commentaire