

Subject:
Can a random function never return some numbers?
Category: Computers > Algorithms Asked by: nediam1234ga 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?  


There is no answer at this time. 

Subject:
Re: Can a random function never return some numbers?
From: probonopublicoga 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: harrysnetga 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^481 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^321 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: nediam1234ga on 26 Oct 2006 12:48 PDT 
harrysnet, thank you very much for your explanation. I understand this much better now. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 