Extending java.util.Random.nextInt(int) into nextLong(long)

Question

In java.util.Random the Oracle implementation of nextInt(int) is as follows:

public int nextInt(int n) {
    if (n <= 0)
        throw new IllegalArgumentException("n must be positive");

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

    int bits, val;
    do {
        bits = next(31);
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    return val;
}

I have a need to do the same thing for longs, but this is not included as part of the class signature. So I extended the class to add this behavior. Here's my solution, and even though I'm pretty sure I have it right, bit-twiddling can subtly fluster even the best of devs!

import java.util.Random;

public class LongRandom extends Random {

    public long nextLong(long n) {
        if (n <= 0)
            throw new IllegalArgumentException("n must be positive");    

        if ((n & -n) == n)  // i.e., n is a power of 2
            return nextLong() & (n - 1); // only take the bottom bits

        long bits, val;
        do {
            bits = nextLong() & 0x7FFFFFFFL; // make nextLong non-negative
            val = bits % n;
        } while (bits - val + (n-1) < 0);
        return val;

    }
}

Have I introduced a subtle bug? Are there improvements to make? What might I need to watch out for?

Answer 1

Try it with n>2^32 and your code will fail. 0x7FFFFFFFL reduces your code to int, breaking your extension to long. You need to use the maximal value of long not int in your mask. i.e. 7FFFFFFFFFFFFFFFL.

Answer 2

You just need to test, It's that simple.
I've tested your code on C#, minus the & 0x7FFFFFFFL; // make nextLong non-negative

(I didn't need that, C# rands are positive)

The results look well distributed on [0,N-1]. So I think code is fine, except for the part I did not test.

Answer 3

There is a similar method in Apache Commons Math: RandomDataGenerator.nextLong(long lower, long upper).

See also: Effective Java, 2nd edition, Item 47: Know and use the libraries (The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.)