Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #34921 > unrolled thread

Re: Will Math.random return 0.0?

Back to article view | Back to comp.lang.java.programmer

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Will Math.random return 0.0? Martin Gregorie <martin@address-in-sig.invalid> - 2016-07-16 19:39 +0000
    Re: Will Math.random return 0.0? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-07-16 16:12 -0400
      Re: Will Math.random return 0.0? Martin Gregorie <martin@address-in-sig.invalid> - 2016-07-16 20:32 +0000
        Re: Will Math.random return 0.0? Martin Gregorie <martin@address-in-sig.invalid> - 2016-07-17 08:00 +0000
      Re: Will Math.random return 0.0? Arne Vajhøj <arne@vajhoej.dk> - 2016-07-16 16:47 -0400
      Re: Will Math.random return 0.0? Marcel Mueller <news.5.maazl@spamgourmet.org> - 2016-07-17 01:03 +0200

#34921 — Re: Will Math.random return 0.0?

On Sat, 16 Jul 2016 15:24:57 +0000, Stefan Ram wrote:

> I wrote the following program.
> 
> public final class Main { public static void main( final
> java.lang.String[] args )
>   { while( java.lang.Math.random() != 0.0 );
>     java.lang.System.out.println( "0.0" ); }}
> 
>   What do you expect it's (average) runtime to be on average hardware?
> 
>   Can we be sure that it will ever terminate?
> 
>   (When the documentation says that »random« might return 0.0, this
>   actually does not say that it ever will do so.)
>
Probably, but it may take some time.

I wrote an instrumented version of your program that accepts the number 
of random values to be generated and (for an eyeball check on Math.random) 
allows you to set the number of buckets that it uses to capture the 
generated random numbers, i.e, 20 buckets splits the range into groups 
that each captures 5% of the range from 0.0 to 1.0. For good measure it 
also captures the smallest and largest random numbers generated.

As the number of randoms generated increases, the min and max values get 
closer to 0.0 and 1.0 and the number of samples in each bucket become 
more even, which is what you'd expect, but even a run generating 10^9 (1 
billion) samples has limits of:
 Min value:     8.878034973847093E-10
 Max value:     0.9999999976070657

By comparison, the limits reached from a 1000 sample run were:
Min value:     7.924107404522207E-5
Max value:     0.9993267012123804

Meanwhile, your original code had been running for a while before I 
developed and played with my extended version and has currently used 
100.5 minutes of MPU time, which is close to 1 hour 40 since its using 
between 99 and 100% of the available CPU time from one of the two cores. 
This is running on a laptop powered by a 1.6 GHz Core Duo with 3GB of RAM 
and running Fedora 23 Linux.

My billion sample run took 132 seconds to run, or 7.6 million samples 
were generated and analysed per second.

I'll leave your code running to see if it stops any time thus evening.  


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [next] | [standalone]

#34922

On 7/16/2016 3:39 PM, Martin Gregorie wrote:
> [...]
> Meanwhile, your original code had been running for a while before I
> developed and played with my extended version and has currently used
> 100.5 minutes of MPU time, which is close to 1 hour 40 since its using
> between 99 and 100% of the available CPU time from one of the two cores.
> This is running on a laptop powered by a 1.6 GHz Core Duo with 3GB of RAM
> and running Fedora 23 Linux.
>
> My billion sample run took 132 seconds to run, or 7.6 million samples
> were generated and analysed per second.
>
> I'll leave your code running to see if it stops any time thus evening.

     Back of the envelope: 2^53 possible numerators (maybe), one of
which is all zero.  7.6 million ~= 2^23 samples per second.  Time to
cycle through all numerators ~= 2^(53-23) ~= 1E9 seconds, which is
just about thirty-four years.  Maybe only half that if we leave out
the analysis, so you should have a definite conclusion by 2033 or so.
And maybe you'll only need to get half way through the full cycle to
hit pay dirt, so I'll pencil you in for, um, 2025.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#34923

On Sat, 16 Jul 2016 16:12:30 -0400, Eric Sosman wrote:

> On 7/16/2016 3:39 PM, Martin Gregorie wrote:
>> [...]
>> Meanwhile, your original code had been running for a while before I
>> developed and played with my extended version and has currently used
>> 100.5 minutes of MPU time, which is close to 1 hour 40 since its using
>> between 99 and 100% of the available CPU time from one of the two
>> cores. This is running on a laptop powered by a 1.6 GHz Core Duo with
>> 3GB of RAM and running Fedora 23 Linux.
>>
>> My billion sample run took 132 seconds to run, or 7.6 million samples
>> were generated and analysed per second.
>>
>> I'll leave your code running to see if it stops any time thus evening.
> 
>      Back of the envelope: 2^53 possible numerators (maybe), one of
> which is all zero.  7.6 million ~= 2^23 samples per second.  Time to
> cycle through all numerators ~= 2^(53-23) ~= 1E9 seconds, which is just
> about thirty-four years.  Maybe only half that if we leave out the
> analysis, so you should have a definite conclusion by 2033 or so.
> And maybe you'll only need to get half way through the full cycle to hit
> pay dirt, so I'll pencil you in for, um, 2025.

Fair enough. Since its 100% use of one core isn't interfering with 
anything else this laptop is doing or eating the battery faster than the 
charger is filling it, I'll leave it running to see if I get lucky.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#34934

On Sat, 16 Jul 2016 20:32:32 +0000, Martin Gregorie wrote:

> On Sat, 16 Jul 2016 16:12:30 -0400, Eric Sosman wrote:
> 
>> On 7/16/2016 3:39 PM, Martin Gregorie wrote:
>>> [...]
>>> Meanwhile, your original code had been running for a while before I
>>> developed and played with my extended version and has currently used
>>> 100.5 minutes of MPU time, which is close to 1 hour 40 since its using
>>> between 99 and 100% of the available CPU time from one of the two
>>> cores. This is running on a laptop powered by a 1.6 GHz Core Duo with
>>> 3GB of RAM and running Fedora 23 Linux.
>>>
>>> My billion sample run took 132 seconds to run, or 7.6 million samples
>>> were generated and analysed per second.
>>>
>>> I'll leave your code running to see if it stops any time thus evening.
>> 
>>      Back of the envelope: 2^53 possible numerators (maybe), one of
>> which is all zero.  7.6 million ~= 2^23 samples per second.  Time to
>> cycle through all numerators ~= 2^(53-23) ~= 1E9 seconds, which is just
>> about thirty-four years.  Maybe only half that if we leave out the
>> analysis, so you should have a definite conclusion by 2033 or so.
>> And maybe you'll only need to get half way through the full cycle to
>> hit pay dirt, so I'll pencil you in for, um, 2025.
> 
> Fair enough. Since its 100% use of one core isn't interfering with
> anything else this laptop is doing or eating the battery faster than the
> charger is filling it, I'll leave it running to see if I get lucky.

Killed at 850 m, 14.17 hours. Didn't stop.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#34924

On 7/16/2016 4:12 PM, Eric Sosman wrote:
> On 7/16/2016 3:39 PM, Martin Gregorie wrote:
>> [...]
>> Meanwhile, your original code had been running for a while before I
>> developed and played with my extended version and has currently used
>> 100.5 minutes of MPU time, which is close to 1 hour 40 since its using
>> between 99 and 100% of the available CPU time from one of the two cores.
>> This is running on a laptop powered by a 1.6 GHz Core Duo with 3GB of RAM
>> and running Fedora 23 Linux.
>>
>> My billion sample run took 132 seconds to run, or 7.6 million samples
>> were generated and analysed per second.
>>
>> I'll leave your code running to see if it stops any time thus evening.
>
>     Back of the envelope: 2^53 possible numerators (maybe), one of
> which is all zero.

But the seed in the underlying RNG only has 48 bits.

>                7.6 million ~= 2^23 samples per second.  Time to
> cycle through all numerators ~= 2^(53-23) ~= 1E9 seconds, which is
> just about thirty-four years.  Maybe only half that if we leave out
> the analysis, so you should have a definite conclusion by 2033 or so.

Much sooner I think.

Arne

[toc] | [prev] | [next] | [standalone]

#34932

On 16.07.16 22.12, Eric Sosman wrote:
>> My billion sample run took 132 seconds to run, or 7.6 million samples
>> were generated and analysed per second.
>>
>> I'll leave your code running to see if it stops any time thus evening.
>
>      Back of the envelope: 2^53 possible numerators (maybe), one of
> which is all zero.  7.6 million ~= 2^23 samples per second.  Time to
> cycle through all numerators ~= 2^(53-23) ~= 1E9 seconds, which is
> just about thirty-four years.  Maybe only half that if we leave out
> the analysis, so you should have a definite conclusion by 2033 or so.

Well, I just wrote the program in C++ which made it faster some orders 
of magnitude. It would take a few days to cycle all 2^48 values on a 3,4 
GHz AMD.

Probably it would be even faster and definitely with less power if I had 
coded it for the Raspberry Pi GPU with 192 parallel threads (all user 
shaders).

> And maybe you'll only need to get half way through the full cycle to
> hit pay dirt, so I'll pencil you in for, um, 2025.

No need to do so. See above.

But in fact things are even more easy:
The Java Random class uses the polynomial
   seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
and to generate the double value it uses only the top 26 or 27 bits of 
the 48 bit seed.

So as soon as seed turns to 0 the next value will be
   (0 * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
which turns out to be just 0xBL.
Both consecutive seeds have the top 27 bits zero. So if no other thread 
extracts a random number meanwhile the result of Random.nextDouble or 
Math.random respectively will be 0.0 in this case.
q.e.d.


Marcel

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web