Opened 3 years ago

Closed 3 years ago

Last modified 2 years ago

#8899 closed bug (fixed)

StdGen does not generate 0

Reported by: novadenizen Owned by: ekmett
Priority: normal Milestone: 7.10.1
Component: libraries/random Version: 7.9
Keywords: Cc: rrnewton, ekmett
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Other Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


genRange for StdGen returns (0,2147483562). However, as far as I can tell, StdGen doesn't generate 0.

This code performs 200 billion iterations of next on a StdGen. I ran it and it output Nothing. The probability that no 0 was generated by chance is approximately e-200/2.147 =~ 10-40.

import System.Random
import Data.Int

find0 :: StdGen -> Int64 -> Maybe Int64
find0 g0 n0 = aux g0 n0 where
    aux _ 0 = Nothing
    aux g r = let (v,g') = next g in
                  if v == 0 then Just (n0 - r + 1)
                            else aux g' (r-1)

main :: IO ()
main = print $ find0 (mkStdGen 1234) 200000000000

Change History (11)

comment:1 Changed 3 years ago by nomeata

Out of curiosity: How long did it take you running that code?

Also, did you you verify that your approach works by looking for, say, 1, 42 or 2147483562?

comment:2 Changed 3 years ago by novadenizen

It ran overnight and I forgot to use time, so I'm not sure. Running with 20 billion iterations took 36 minutes on my linode, though, so I would expect it took about 6 hours.

I just now reran this tool looking for v == 3 and it output Just 871055575, which is reasonable.

comment:3 Changed 3 years ago by nomeata

Hmm, I don’t have the rights to put other people on CC on this ticket. Ryan (random maintainer), are you reading this?

comment:4 Changed 3 years ago by hvr

Cc: rrnewton added

I've enabled auto-CC'ing rrnewton for the random component, so he will get spammed automatically in future :-)

comment:5 Changed 3 years ago by rrnewton

Hi all, late to the party but I'll take a look.

comment:6 Changed 3 years ago by thomie

The StdGen indeed never generates 0.

This follows from the following line in the function stdNext (z' is the next generated Int):

z' = if z < 1 then z + 2147483562 else z

I checked the paper, and this is as intended. The range should be [1, 2147483562]. novadenizen's script also finds these:

Just 885777925 -- v == 1
Just 2217242596 -- v == 2147483562

Here's a pull request.

comment:7 Changed 3 years ago by thomie

Milestone: 7.10.1
Status: newpatch

comment:8 Changed 3 years ago by simonpj

Cc: ekmett added
Owner: set to ekmett

Adding Edward K, since this is really a Core Libraries matter.


comment:9 Changed 3 years ago by thoughtpolice

Status: patchupstream

comment:10 Changed 3 years ago by thomie

Resolution: fixed
Status: upstreamclosed

comment:11 Changed 2 years ago by ekmett

Fixed in random 1.1.

Note: See TracTickets for help on using tickets.