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

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?

-
You can find some alternatives on SO. – avip Nov 17 '12 at 5:20
Unlike Microsoft, Sun got that code right. Nice. – CodesInChaos Nov 18 '12 at 13:24

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.

-

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.

-
The problem with testing is that it’s categorically impossible to prove correctness through it. Your test in particular fails to find failing cases which another answer has found. – Konrad Rudolph Nov 18 '12 at 14:28
That's nonsense. Did you read my post? You don't test to 'prove correctness', that's for the academics. You test to find faults. – avip Nov 18 '12 at 21:58
I actually think my previous comment was premature. But your “that’s for academics” dismissal is ridiculous. – Konrad Rudolph Nov 18 '12 at 22:20
So style and phrasing aside, we're on accord on the subject. – avip Nov 19 '12 at 4:04

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.)

-