Google Answers Logo
View Question
 
Q: Can a random function never return some numbers? ( No Answer,   3 Comments )
Question  
Subject: Can a random function never return some numbers?
Category: Computers > Algorithms
Asked by: nediam1234-ga
List Price: $15.00
Posted: 26 Oct 2006 02:06 PDT
Expires: 26 Oct 2006 12:48 PDT
Question ID: 777043
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 :)
Answer  
There is no answer at this time.

Comments  
Subject: Re: Can a random function never return some numbers?
From: probonopublico-ga on 26 Oct 2006 07:00 PDT
 
I can say from experience that two numbers will never come up:  and .

Unless, of course, someone has nobbled the program.
Subject: Re: Can a random function never return some numbers?
From: harrysnet-ga on 26 Oct 2006 11:41 PDT
 
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.
Subject: Re: Can a random function never return some numbers?
From: nediam1234-ga on 26 Oct 2006 12:48 PDT
 
harrysnet, thank you very much for your explanation. I understand this
much better now.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy