CODEWITHSUNDEEP
javarandom
jl90
jl90

Reputation: 649

Unbiased random integer generator

After reading some posts, I've found out that using Math.random() in Java to generate an integer is somehow biased.

I came across an algorithm in this post:

Unbiased random number generator using a biased one

It generates an unbiased result between 0 and 1 and I wanted to use it for my program.

However, I'm trying to create an unbiased generator between 0 and a certain value (e.g. 7) in Java but I'm not really sure that if this algorithm works for a range of numbers.

If it doesn't, what must I do in order to create an unbiased integer generator that I want?

Upvotes: 0

Views: 1066

Answers (5)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

I believe you misread those posts. The one you linked essentially says that you shouldn't use random.nextInt() % max, which is indeed biased; so this approach is very naive. However, if you look at the documentation or source code of Javas nextInt(max) function, it is more clever than that. Probably unbiased enough for you. Just learn more about the Java API, it has a lot of functionality...

The example discussed in detail generates a single bit in an unbiased way, not an unbiased double random between 0 and 1!

I'm not convinced that Java random generator is substantially biased in the way that you are concernced with. But it certainly is not a high-quality random, because it needs to be fast for most users. If you want a high entropy random, try using the high-quality random sources of your operating system.

Either way, If you want a random number from 0 to 7 using the method linked from your post (which probably is total overkill!), do this:

int bit1 = generateOneBitOfRandom();
int bit2 = generateOneBitOfRandom();
int bit3 = generateOneBitOfRandom();
int zerotoseven = (bit1 << 2) + (bit2 << 1) + bit3;

// Probably at least as good is the proper Java API:
Random random = new Random();
int zerotoseven2 = random.nextInt(8);

Again, most likely, java.util.Random nextInt(8) will be good enough for you. Unless you are doing cryptography. Then you really should consider just reading a byte from /dev/random, which may be accessing a hardware entropy pool, if your CPU or mainboard has such features (just hope that one isn't biased / bias cancelled). Which is most likely what Javas SecureRandom does. Again an example that the Java API is probably much more clever than you think it is.

Upvotes: 2

Daniel Kaplan
Daniel Kaplan

Reputation: 67340

You can just use Random.nextInt(int). For your needs, use new Random().nextInt(8). As it says in the documentation:

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive)

But actually, I think you could have used Math.random() all along. Its documentation says:

When this method is first called, it creates a single new pseudorandom-number generator, exactly as if by the expression new java.util.Random

The source code for Math.random() is:

public static double random() {
    if (randomNumberGenerator == null) initRNG();
    return randomNumberGenerator.nextDouble();
}

And the documentation for nextDouble also says:

Returns the next pseudorandom, uniformly distributed double value between 0.0 and 1.0

Upvotes: 2

Steven Schlansker
Steven Schlansker

Reputation: 38526

You need to cite the reference that claims that the Java Math.random() is biased, and in exactly what way. That would be a huge problem, as this is a very core portion of the Java standard library.

Java provides SecureRandom which is more appropriate for cryptographic-strength random number generation. To use this to generate a number between 0 and N, you can use the same algorithm presented in the Random.nextInt(int) documentation but with SecureRandom instead.

Don't implement your own random number generator algorithm unless you are willing to go to the trouble to prove that it is better than the stock one. It is very hard to create a good quality algorithm and you are very likely to just make the problem worse.

Upvotes: 4

Jack Harkness
Jack Harkness

Reputation: 810

Try this:

int randomizer(int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}

It is a modified version of the other algorithm you linked to.

Upvotes: 1

David says Reinstate Monica
David says Reinstate Monica

Reputation: 20129

If it only works from 0 to 1 just multiply whatever it gives you by 7, and you will have an unbiased random number from 0 to 7.

Upvotes: -1

Related Questions