mardi 2 avril 2019

About implementation code for a uniform function

I was checking source code of StdRandom's uniform

And confused by part of its implementation.

The source code is below:

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;
    }

So my problem is about "// reject over-represented candidates" section

What is the meaning of (u+m - (r=u%n) < 0L) here? I can only think of one situation when this expression become true, that is when (u + m) become too big and overflow to be a negative number. But why then? Or am I wrong at very start?




Aucun commentaire:

Enregistrer un commentaire