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

Groups > comp.lang.java.programmer > #34920 > 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? Arne Vajhøj <arne@vajhoej.dk> - 2016-07-16 14:37 -0400
    Re: Will Math.random return 0.0? Arne Vajhøj <arne@vajhoej.dk> - 2016-07-16 16:51 -0400

#34920 — 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?
>
>   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.)

The seed algorithm is:

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

and given that:

mod(0x5DEECE66D,4) is 1
0xB is odd
& ((1L << 48) - 1) must be equivalent to mod pow(2,48)

then the algorithm should have full cycle aka seed
will have all values including zero.

so if nextDouble() just returned seed/pow(2,48) then
it will return 0.0 occasionally.

But it does not. Instead it uses:

return (((long)next(26) << 27) + next(27)) / (double)(1L << 53);

So it will only return 0.0 if the high 26 bits of seed
and after update the high 27 bits of seed are both zero.

Now my math skills are not good enough to evaluate
whether that is indeed the case or not.

The above has pow(2,53) potential values but given the
seed cycle of pow(2,48) and the need for 2 calls, then
it will only be able to return pow(2,47) different values.

So odds is only 1:64 for returning zero for the math challenged
like me.

But you could test it by iterating pow(2,47) times. Which should
be computable.

Alternative wait for somebody with better math skills to solve
it analytical.

BTW, I think the question is rather pointless. If the difference
between 0.0 and almost 0.0 matters then double is not the right
data type in the first place.

Arne

[toc] | [next] | [standalone]

#34925

On 7/16/2016 2:37 PM, Arne Vajhøj wrote:
> On 7/16/2016 11:24 AM, Stefan Ram wrote:
> The seed algorithm is:
>
> seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
>
> and given that:
>
> mod(0x5DEECE66D,4) is 1
> 0xB is odd
> & ((1L << 48) - 1) must be equivalent to mod pow(2,48)
>
> then the algorithm should have full cycle aka seed
> will have all values including zero.
>
> so if nextDouble() just returned seed/pow(2,48) then
> it will return 0.0 occasionally.
>
> But it does not. Instead it uses:
>
> return (((long)next(26) << 27) + next(27)) / (double)(1L << 53);
>
> So it will only return 0.0 if the high 26 bits of seed
> and after update the high 27 bits of seed are both zero.
>
> Now my math skills are not good enough to evaluate
> whether that is indeed the case or not.
>
> The above has pow(2,53) potential values but given the
> seed cycle of pow(2,48) and the need for 2 calls, then
> it will only be able to return pow(2,47) different values.

Hmm. Eric's post just got me thinking.

A given seed will only give pow(2,47) doubles in
a cycle.

But there must be two possible double cycles meaning
that the answer (0.0 possible) may depend on the initial
seed.

That may complicate the test a bit.

Arne

[toc] | [prev] | [standalone]

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

csiph-web