Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Will Math.random return 0.0? Date: Sun, 17 Jul 2016 08:06:51 -0400 Organization: A noiseless patient Spider Lines: 53 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Sun, 17 Jul 2016 12:06:59 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="22e5ab429c5a4bb738666b9c52e40d69"; logging-data="1031"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+dcqOonwd1K6/+lYTWWBGO" User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 In-Reply-To: Cancel-Lock: sha1:0nKFYwe/JW3idT78Yz+QTuuFjNc= Xref: csiph.com comp.lang.java.programmer: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