anyone help me understand java nextInt(int)?

B

briteguy

Jdk code for nextInt(int) 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 am not sure why the condition:
while(bits - val + (n-1) < 0)
would be necessary to block uneven numbers?

Anyone could explain more on this? Thanks,
 
J

Jon Gómez

John B. Matthews wrote:
[...]
The API documentation explains more: [..]
As does this article:

<http://en.wikipedia.org/wiki/Linear_congruential_generator>

I was going to say the same thing, but then I was unsure. The OP wasn't
asking about the implementation of next(), but that of nextInt(), in
which a pseudorandom number generator is already available and its
implementation can be safely ignored. Then again, perhaps that
documentation will help with the question of re-tailoring an existing
probability distribution, and maybe there is an answer somewhere in
that. I think I may stare at the code a while longer myself, when I get
a chance.

Jon.
 
J

Jon Gómez

John B. Matthews wrote:
[...]
The API documentation explains more: [..]
As does this article:

<http://en.wikipedia.org/wiki/Linear_congruential_generator>

I was going to say the same thing, but then I was unsure. The OP wasn't
asking about the implementation of next(), but that of nextInt(), in
which a pseudorandom number generator is already available and its
implementation can be safely ignored. Then again, perhaps that
documentation will help with the question of re-tailoring an existing
probability distribution, and maybe there is an answer somewhere in
that. I think I may stare at the code a while longer myself, when I get
a chance.

Jon.
 
J

Joshua Cranmer

briteguy said:
I am not sure why the condition:
while(bits - val + (n-1) < 0)
would be necessary to block uneven numbers?

Here is a simple explanation: the implementation of the RNG uniformly
distributes number among the lower 31 bits. The naive implementation
would merely modulo the number by the target high value, which does not
produce a correct uniform distribution, as the number 1 will be more
frequent than the number (n-1), for example.

Think of it as trying to determine random numbers by flipping coins. If
you have two coins, you generate four equally likely results: HH, HT,
TH, TT. Suppose you only want to choose from values 0, 1, and 2. The
naive implementation (using the modulus operator) would map:
HH -> 0
HT -> 1
TH -> 2
TT -> 0

which is obviously not uniform. To get a uniform distribution, you need
to take the extra result, TT, and make it invalid value so that you flip
the coins again. This is what the code is doing, in essence--getting
another random number if it is in the excess at the end.
 
B

briteguy

Thanks, that explanation helps plus the info about linear congruential
generator. It is a bit mind-bending for me to understand. But now I am
starting to see the logic.
 
J

John B. Matthews

Jon Gómez said:
John B. Matthews wrote:
[...]
The API documentation explains more: [..]
As does this article:

<http://en.wikipedia.org/wiki/Linear_congruential_generator>

I was going to say the same thing, but then I was unsure. The OP
wasn't asking about the implementation of next(), but that of
nextInt(), in which a pseudorandom number generator is already
available and its implementation can be safely ignored. Then again,
perhaps that documentation will help with the question of
re-tailoring an existing probability distribution, and maybe there is
an answer somewhere in that. I think I may stare at the code a while
longer myself, when I get a chance.

The generator is an LCG. IIUC, the "lower-order bits of the generated
sequence have a far shorter period than the sequence as a whole if m is
set to a power of 2." After special-casing n as a power of two, the API
explains that the loop repeats until it finds a sufficient number of
low-order bits for a given value of n.

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

I'd welcome any additional insight.
 
J

Jon Gómez

John said:
The generator is an LCG. IIUC, the "lower-order bits of the generated
sequence have a far shorter period than the sequence as a whole if m is
set to a power of 2." After special-casing n as a power of two, the API
explains that the loop repeats until it finds a sufficient number of
low-order bits for a given value of n.

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

I'd welcome any additional insight.



Oh no, I'm at fault. I looked at the class description, where I did
pick up the LCG info and the Knuth reference, but I skipped over the
nextInt(int) method description, of all things. Thanks for pointing out
that the API had more to tell me!
Jon.
 
J

Jon Gómez

Patricia said:
If we were doing unbounded range arithmetic, (bits - value + (n-1))
would never be negative. The condition is really asking whether it is at
least 2^31, but if it is it will overflow and look negative.

To simplify things, and avoid dealing with integer overflow, I'm going
to rewrite the code supposing n is in the range 0 through 7, and we are
going to use next(3) to get a number in the range 0 through 7.

do {
bits = next(3); // 0 <= bits && bits < 8
val = bits % n; // 0 <= val && val < n
} while (bits - val + (n-1) >= 8)

In this miniature case, we can look at all the results for e.g. n=3.

bits = 0, val = 0, bits - val + (n-1) = 2
bits = 1, val = 1, bits - val + (n-1) = 2
bits = 2, val = 2, bits - val + (n-1) = 2
bits = 3, val = 0, bits - val + (n-1) = 5
bits = 4, val = 1, bits - val + (n-1) = 5
bits = 5, val = 2, bits - val + (n-1) = 5
bits = 6, val = 0, bits - val + (n-1) = 8
bits = 7, val = 1, bits - val + (n-1) = 8

Without the while code, 0 and 1 would each be selected for 3 of the
possible next(3) results, but 2 would only be selected for 2 of them.
Instead of returning each result with probability 1/3, they would have
probabilities 3/8, 3/8, 1/4.

The while loop throws back results from the incomplete slice containing
only 6 and 7, keeping any result from the two complete slices, 0 through
2 and 3 through 5.

bits - val is the start of the slice containing the result, the value in
that slice that would have mapped to zero. (bits - value + (n-1)) is the
end of the slice, the value that should map to n-1. If it is out of the
range of values next could have returned, then the slice is incomplete,
and no value from it can be used. Throw it back and try again.

Patricia

That is a wonderfully lucid explanation!
Jon.
 
J

John B. Matthews

Jon Gómez said:
Oh no, I'm at fault. I looked at the class description, where I did
pick up the LCG info and the Knuth reference, but I skipped over the
nextInt(int) method description, of all things. Thanks for pointing
out that the API had more to tell me!

Excellent! Having stumbled over poor implementations in the past, I
value the transparency of the API in this. I also found Patricia's
explication in this thread particularly enlightening.

I couldn't help but notice a small regression in the current API: Knuth
discusses random numbers in The Art of Computer Programming, Volume 2:
Seminumerical Algorithms, not Volume 3, which is devoted to Sorting and
Searching:

<http://java.sun.com/j2se/1.5.0/docs/api/java/util/Random.html#next(int)>
<http://java.sun.com/javase/6/docs/api/java/util/Random.html#next(int)>
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top