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

Groups > comp.lang.java.programmer > #34937

Re: Will Math.random return 0.0?

Show key headers only | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web