Opened 18 months ago

Closed 13 months ago

Last modified 12 months 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 Revisions:

Description

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 18 months 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 18 months 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 18 months 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 17 months 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 17 months ago by rrnewton

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

comment:6 Changed 14 months 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 14 months ago by thomie

  • Milestone set to 7.10.1
  • Status changed from new to patch

comment:8 Changed 14 months ago by simonpj

  • Cc ekmett added
  • Owner set to ekmett

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

Simon

comment:9 Changed 13 months ago by thoughtpolice

  • Status changed from patch to upstream

comment:10 Changed 13 months ago by thomie

  • Resolution set to fixed
  • Status changed from upstream to closed

comment:11 Changed 12 months ago by ekmett

Fixed in random 1.1.

Note: See TracTickets for help on using tickets.