Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.