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

Groups > comp.lang.java.programmer > #34913 > 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? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-07-16 12:49 -0400
    Re: Will Math.random return 0.0? Thomas Richter <thor@math.tu-berlin.de> - 2016-07-16 18:53 +0200
      Re: Will Math.random return 0.0? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-07-16 13:11 -0400
        Re: Will Math.random return 0.0? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-07-17 08:06 -0400
      Re: Will Math.random return 0.0? Arne Vajhøj <arne@vajhoej.dk> - 2016-07-16 14:17 -0400

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

On 7/16/2016 11:24 AM, 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?

     Longer than my attention span.

>   Can we be sure that it will ever terminate?

     Yes.

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

[toc] | [next] | [standalone]

#34915

Am 16.07.2016 um 18:49 schrieb Eric Sosman:

> 
>>   Can we be sure that it will ever terminate?
> 
>     Yes.
> 
No. A couple of well-understood "random" generators are simply of the form

x_n = (x_{n-1} * a) mod b

with a and b some relatively prime numbers. These are not particularly
good generators, but often simple to implement and fast - even more so
if b is (one minus) a power of two.

In such a case, zero is a trivial period of the generator, and for that
reason, the generator is never initialized by zero. It then can be seen
that it never reaches zero either (given the ring Z_b has no zero dividers).

Random() on such a core random generator would return the number x_n
divided by b, and hence the output would never be zero.

Again, whehter this generator is an acceptable generator for Java
implementations I cannot say, but it is at least a well-studied (not-so,
but sufficiently) random generator that has been used in the past.

Greetings,
	Thomas

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

#34916

On 7/16/2016 12:53 PM, Thomas Richter wrote:
> Am 16.07.2016 um 18:49 schrieb Eric Sosman:
>
>>
>>>   Can we be sure that it will ever terminate?
>>
>>     Yes.
>>
> No. A couple of well-understood "random" generators are simply of the form
>
> x_n = (x_{n-1} * a) mod b

     ... and Math.random() is *documented* to use a different generator.

     The question of whether Math.random() will ever return 0.0 boils
down to whether two successive calls to Random#next() will return 27
and 26 (respectively) zero bits from among the 96 bits produced by
the *documented* base algorithm.  I lack sufficient mathematical
prowess to say whether this is possible.

     ... but I claim, nonetheless, that Stefan's program will terminate:

     - It may terminate on its own by generating 0.0, or

     - Whoever is running it will tire of the exercise and stop it, or

     - The JVM, O/S, hardware, or power will fail.

No matter which of these happens, the program will have terminated.

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

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

#34937

On 7/16/2016 1:11 PM, Eric Sosman wrote:
> [...]
>     The question of whether Math.random() will ever return 0.0 boils
> down to whether two successive calls to Random#next() will return 27
> and 26 (respectively) zero bits from among the 96 bits produced by
> the *documented* base algorithm.  I lack sufficient mathematical
> prowess to say whether this is possible.

     It turns out not much mathematical prowess is required.  Random
scrambles its internal 48-bit state with a linear congruential full-
period PRNG -- that is, the internal state runs through all values
from 0 through 0xffffffffffffL in some sequence.  Random#nextDouble()
(on which Math.random() relies) uses the high-order 27 and 26 bits,
respectively, of two successive states I will call First and Second.
So to find out whether these 53 bits can be all zeroes, it suffices to
run through the possible First states and compute their corresponding
Second states.

     There are 2**(48-27) ~= two million First states with 27 high-order
zero bits, and a short program can compute their Seconds rapidly.
An exhaustive search ("BUILD SUCCESSFUL (total time: 0 seconds)" on
my machine) shows that there does, in fact, exist a pair of successive
internal states with 27 and 26 high-order zeroes, namely

	0 is followed by 11

... and that this is the only such pair.  Further, it finds that
there are no triples, that is, no sequence of three successive states
yielding the required quantity of high-order zeroes.

     ERGO:

     1) It is possible that Math.random() can return 0.0, exactly

     2) ... but it is not certain, because the initial state of the
internal Random is not under the programmer's control.  If state 0
turns up on the 1st, 3rd, 5th, ... call to Random#next() then 11 will
crop up on the next and 0.0 will result.  But if state 0 turns up on
the 2nd, 4th, 6th, ... call then 0.0 will never result (that's why
the "no triples" observation is important).

     SO:

     Stefan's program will in fact terminate.  50% of the time it
will terminate of its own volition after generating no more than
2**47 ~= 1.4E14 values (at a billion per second this will take
no more than 39 hours; adjust as needed).  The other 50% of the
time it will run until terminated by external conditions.


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

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

#34918

On 7/16/2016 12:53 PM, Thomas Richter wrote:
> Am 16.07.2016 um 18:49 schrieb Eric Sosman:
>>>   Can we be sure that it will ever terminate?
>>
>>     Yes.
>>
> No. A couple of well-understood "random" generators are simply of the form
>
> x_n = (x_{n-1} * a) mod b
>
> with a and b some relatively prime numbers. These are not particularly
> good generators, but often simple to implement and fast - even more so
> if b is (one minus) a power of two.
>
> In such a case, zero is a trivial period of the generator, and for that
> reason, the generator is never initialized by zero. It then can be seen
> that it never reaches zero either (given the ring Z_b has no zero dividers).
>
> Random() on such a core random generator would return the number x_n
> divided by b, and hence the output would never be zero.

The argument does not hold water as it is trivial to subtract one
to get a random number that can be zero.

But anyway the Java random number generator is documented to have
a non-zero add part, so ...

Arne

[toc] | [prev] | [standalone]

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

csiph-web