[GHC] #8899: StdGen does not generate 0
#8899: StdGen does not generate 0 ------------------------------------+------------------------------------- Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: Other Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- `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^''. {{{#!haskell 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 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (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`? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (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? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by hvr): * cc: rrnewton (added) Comment: I've enabled auto-CC'ing rrnewton for the `random` component, so he will get spammed automatically in future :-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by rrnewton): Hi all, late to the party but I'll take a look. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by thomie): The `StdGen` indeed never generates `0`. This follows from the following line in the function `stdNext` (`z'` is the next generated `Int`): {{{#!haskell 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: {{{#!haskell Just 885777925 -- v == 1 Just 2217242596 -- v == 2147483562 }}} Here's a [https://github.com/haskell/random/pull/7 pull request]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------ Reporter: novadenizen | Owner: Type: bug | Status: patch Priority: normal | Milestone: 7.10.1 Component: libraries/random | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: Other | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by thomie): * status: new => patch * milestone: => 7.10.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------- Reporter: | Owner: ekmett novadenizen | Status: patch Type: bug | Milestone: 7.10.1 Priority: normal | Version: 7.9 Component: | Keywords: libraries/random | Operating System: Unknown/Multiple Resolution: | Type of failure: Other Differential Revisions: | Test Case: Architecture: | Blocking: Unknown/Multiple | Difficulty: Unknown | Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Changes (by simonpj): * cc: ekmett (added) * owner: => ekmett Comment: Adding Edward K, since this is really a Core Libraries matter. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------- Reporter: | Owner: ekmett novadenizen | Status: upstream Type: bug | Milestone: 7.10.1 Priority: normal | Version: 7.9 Component: | Keywords: libraries/random | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thoughtpolice): * status: patch => upstream -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------- Reporter: | Owner: ekmett novadenizen | Status: closed Type: bug | Milestone: 7.10.1 Priority: normal | Version: 7.9 Component: | Keywords: libraries/random | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thomie): * status: upstream => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8899: StdGen does not generate 0 -------------------------------------+------------------------------------- Reporter: | Owner: ekmett novadenizen | Status: closed Type: bug | Milestone: 7.10.1 Priority: normal | Version: 7.9 Component: | Keywords: libraries/random | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by ekmett): Fixed in random 1.1. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8899#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC