To begin with I want to say that I know that there is nothing "random"
in computers and I know pretty well how random is usually done (by shifting
and stuff...).

But I am wondering about the random generator in java (well.. could be
in any language), in java the next random number is generated with:

 synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int)(seed >>> (48 - bits));
 }

(the whole class documentation can be seen at
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Random.html )


I can see that this creates very different numbers for each call to
the function, and I know they always say that each value have
"approximately" the same change to come up (since they don't have the
same change to come up!).

But lets say we pass the number 32 to the function, can I be sure that
for example the number 123456789 will ever show up (if I call the
function often enough!) or could there be some numbers that are never
generated?

---

Clarification of Question by nediam1234-ga on 26 Oct 2006 02:20 PDT

I of course meant to write 'chance' where I wrote 'change' in the text above :)

I can say from experience that two numbers will never come up: ½ and ¼.

Unless, of course, someone has nobbled the program.

This type of algorithm is a linear congruential generator, as it mentions in 
the link that you give. The Knuth reference is very good, see if you can find 
it in your library.

Btw this is an excellent series of books (it is old, but not dated). It is 
almost continuously in print (e.g. check Amazon), so I would recomment anyone 
to buy it if at all possible (it is very expensive though)

Back to the problem, you may also want to check

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

for discussion of the algorithm. Checking the criteria there for full period 
you see that they are met, so the 48 bit seed will indeed take all possible 
values 0,...,2^48-1 and then loop, although the loop is 2^48=2,8*10^14 steps 
long.

If you pass 32 to the function you get a shift to the right by 16 bits, or a 
division by 2^16. The value returned is 32 bits unsigned (up to more than 
4 billion) and each number in the range, up to 2^32-1 will come up 2^16 times 
in the 2^48 long period at irregural intervals. So will your number since it 
is in the given range.

harrysnet, thank you very much for your explanation. I understand this
much better now.