• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Random between 0 and 1 inclusive

 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tim Holloway wrote:The solution (nexInt(n)) / (double) (n - 1)) is questionable because if the random function being used is what I suspect it is (I haven't read the actual official JVM source, but I'm assuming it's based on Knuth), then the nextInt(n) method is actually floor(nextValue(n)*n) in pseudo-code.


It is indeed based on Knuth, but all methods in Random are based on next(#bits), which is described here, and I don't see any mention of floor().

It does however say that the general contract is that for any value up to 32, the "bits of the returned value will be (approximately) independently chosen bit values, each of which is (approximately) equally likely to be 0 or 1".

In other words, invoking the floating-point random function


But it isn't a floating-point function; it returns a specified number of random bits as an int, and nextInt() actually does a bit of massaging to correct some well-known defects of LCGs.

And I'm not saying that my solution is perfect; but it only assumes that the authors of nextInt() knew what they were doing. And I've also been able to prove (at least to my satisfaction) that both extremes occur with "expected" frequency.

Winston
 
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
sorry about the delay.... I'd been sidetracked! I do appreciate all of the input though a lot (most?) of it was over my head .... anyway, i think my post wasn't clear enough. It really is not a matter of precision in this particular case. Rather the conditions of the "problem" stated that "if "0", then no possibility" and if "1" 100% of the time". I think it was a bad set of directions and bypassed it after finding nothing in Java to get an inclusive 1.... and I do see why. That would make no sense, because if 0 is inclusive, then 1 is past the upper limit. Sorrowful example, but I think it's like the 1st century can only go up to midnight of the 99th year.... once it reaches 100, it's the next century. Thank you once again. I sure see a lot of brain power from you all... I am amazed in fact.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ted Schrey wrote:sorry about the delay.... I'd been sidetracked! I do appreciate all of the input though a lot (most?) of it was over my head .... anyway, i think my post wasn't clear enough. It really is not a matter of precision in this particular case. Rather the conditions of the "problem" stated that "if "0", then no possibility" and if "1" 100% of the time". I think it was a bad set of directions and bypassed it after finding nothing in Java to get an inclusive 1.... and I do see why. That would make no sense, because if 0 is inclusive, then 1 is past the upper limit. Sorrowful example, but I think it's like the 1st century can only go up to midnight of the 99th year.... once it reaches 100, it's the next century. Thank you once again.


Glad to help; it was a fun question.

And the fact is that you can get a result that includes both 0.0 and 1.0; it's just not as straightforward as you might think - and, as you already discovered, not available via nextDouble().

However, as I tried to explain, there's no guarantee that nextDouble() would ever return 0.0 either, even though it's theoretically in the range - and a test to find out whether it does could take a very long time. .

Winston
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ted Schrey wrote:. . . it's like the 1st century can only go up to midnight of the 99th year.... once it reaches 100, it's the next century. . . .

Bad analogy, I am afraid. Year numbers are like counting numbers; you go from 1 to 100. Imagine that Math#random returned a value between 0.000000000000001 and 1.0 inclusive.
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
?

Didn't we start counting the 20th century at 1900, and ended at 1999?
 
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:?

Didn't we start counting the 20th century at 1900, and ended at 1999?



Nope, 20th century began January 1, 1901 and ended December 31, 2000
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Really? Wow.

I realize this makes sense because we started counting at 1, but the programmer inside me weeps.
 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote:. . . 20th century . . . 2000

Otherwise the 20th century would have had no years starting 20.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote:

Stephan van Hulst wrote:?

Didn't we start counting the 20th century at 1900, and ended at 1999?



Nope, 20th century began January 1, 1901 and ended December 31, 2000




Funnily enough, the 3th millennium started January 1, 2001 so all the 2000 celebretions were a year early.
 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:. . . the programmer inside me weeps.

It is only since the advent of numeric datatypes limited in the number of digits available that counting from 0…99 became necessary. On an old cash register which I remember from when I was little, it might have been impossible to ring up £2. It was however possible to ring up £1/19/11¾ which was the largest amount possible with the number of wheels/labels available to show the sum.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A.J. Côté wrote:Funnily enough, the 3th millennium started January 1, 2001 so all the 2000 celebretions were a year early.




Campbell Ritchie wrote:On an old cash register which I remember from when I was little, it might have been impossible to ring up £2. It was however possible to ring up £1/19/11¾ which was the largest amount possible with the number of wheels/labels available to show the sum.


 
Saloon Keeper
Posts: 27763
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
However, as I tried to explain, there's no guarantee that nextDouble() would ever return 0.0 either, even though it's theoretically in the range - and a test to find out whether it does could take a very long time. .



Actually there is a guarantee that nextDouble can return 0.0. It's part of the spec. The difference between can and will is what makes it probability. If the probability of getting 0.0 back was itself 0, then that would be a certainty, and therefore a violation of the spec.

Now that we know that the actual requirement ("All You Have To Do Is..." was simply to return a random value of 0 or 1, of course, the solution collapses down to nextInt(2) which gives precisely 50% probability for each possible outcome. And once again, we get reminded that users aren't always precise in what they ask for.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tim Holloway wrote:Actually there is a guarantee that nextDouble can return 0.0. It's part of the spec.


Maybe so, but it's unenforceable in real life, since it's practically impossible to test. In fact, I'd care to bet that the probability of it actually returning 0.0 is less than 1 in 32 (2⁴⁸ / 2⁵³ - and that would assume that Random's LCG generates a perfect spread of numbers for its seed, which seems highly unlikely).

The problem is that I only suspect this to be true; I can't back it up with theory. I also don't know whether it makes any difference how the generator produces its "random" 53-bit number (in Random's case: two calls to next(26) and next(27)). I don't think it does, but I can't back it up.

These are the times when I really wish I'd taken higher Maths.

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:...and that would assume that Random's LCG generates a perfect spread of numbers for its seed, which seems highly unlikely).


For anyone who's interested (Ted, Tim?), I discovered this page about a family of RNGs called "Xorshift", the smallest of which has a maximal (and possibly actual) period of 2⁶⁴−1, which would make it eminently suitable for generating a double that does return 0.0 (eventually).

TBH, they look so simple that one wonders how it took so long to discover them. They would also appear to be statistically better than LCGs, no slower (at least not so you'd notice), and take up very little more space - which begs the the question: Why haven't they been retrofitted to Random?

Not that it makes a big difference, since Random can be subclased. This page explains a bit about them, and shows a possible Java implementation here.

It should be said that the last site still describes them as a "medium quality" PRNG, although they do pass a lot more of the major tests than LCGs do.

HIH

Winston
 
Ranch Hand
Posts: 789
Python C++ Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can get a truly random number by reading milliseconds from a timer or clock register that rolls over, if it's read at random times such as a person coming up and interacting with the program.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not really. A timer has predictable properties, or otherwise produces values with a low entropy. For 'true randomness' you need specialized hardware that measures certain types of noise.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Guillermo Ishi wrote:You can get a truly random number by reading milliseconds from a timer or clock register that rolls over, if it's read at random times such as a person coming up and interacting with the program.


Actually not, for all the reasons Stephan supplied. Long.reverse(milliseconds) would probably be a bit better in terms of "predictability", and nanoTime() is actually a much better "timer" to use - forward or backward.

Timers are often used as initial seeds for RNGs though.

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:For anyone who's interested (Ted, Tim?), I discovered this page about a family of RNGs called "Xorshift"...


And a bit of further search found me this site by Sebastiano Vigna, which goes into the subject in a lot more detail and links lots of code examples (in C unfortunately), including one for a very fast RNG with 1024 bits of state, which might interest people (like me) who want an RNG that can deliver every combination of a shuffled 52-card deck (≈2²²⁶ permutations) with equal probability.

It also highlighted (to me, at least) that there is a new class in version 8 called SplittableRandom, which would appear to be an "improved" Random.

HII

Winston
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic