GHC issueshttps://gitlab.haskell.org/ghc/ghc/issues2019-07-07T19:18:00Zhttps://gitlab.haskell.org/ghc/ghc/issues/427Random.StdGen slowness2019-07-07T19:18:00ZremitRandom.StdGen slowness```
Two (performance) problems in one:
{-# OPTIONS -fffi #-}
module Main (main) where
import Control.Monad
import Random
foreign import ccall unsafe "random" _crandom :: IO Int
randomInt :: (Int, Int) -> IO Int
randomInt (min,max) = do
n <- _crandom
return $ min + n `rem` range
where
range = max - min + 1
main = replicateM_ (5*10^6) $ do
x <- randomRIO (0::Int,1000) :: IO Int
x `seq` return ()
return ()
First, without the "seq" at the end, hardly anything is
evaluated and we're building huge amounts of thunks.
Three ideas about this one:
- Blame the user :)
- data StdGen = StdGen !Int !Int
Use strict fields in StdGen. Doesn't actually help
(at least in this example).
- Force evaluation of the StdGen in getStdRandom.
Does help in this example, but also changes behaviour
of the library:
x <- randomRIO undefined
currently dies only when x (or the result of a later
randomRIO) is evaluated. This change causes it to die
immediately.
Second, even _with_ the "seq", replacing "randomRIO" by
"randomInt" speeds the thing up with a factor of about
30. (2 to 3.6, in a "real world" university practicum
exercise of 900 lines of code)
Even given the fact that they're not really doing the
same thing, this seems rather much :(
``````
Two (performance) problems in one:
{-# OPTIONS -fffi #-}
module Main (main) where
import Control.Monad
import Random
foreign import ccall unsafe "random" _crandom :: IO Int
randomInt :: (Int, Int) -> IO Int
randomInt (min,max) = do
n <- _crandom
return $ min + n `rem` range
where
range = max - min + 1
main = replicateM_ (5*10^6) $ do
x <- randomRIO (0::Int,1000) :: IO Int
x `seq` return ()
return ()
First, without the "seq" at the end, hardly anything is
evaluated and we're building huge amounts of thunks.
Three ideas about this one:
- Blame the user :)
- data StdGen = StdGen !Int !Int
Use strict fields in StdGen. Doesn't actually help
(at least in this example).
- Force evaluation of the StdGen in getStdRandom.
Does help in this example, but also changes behaviour
of the library:
x <- randomRIO undefined
currently dies only when x (or the result of a later
randomRIO) is evaluated. This change causes it to die
immediately.
Second, even _with_ the "seq", replacing "randomRIO" by
"randomInt" speeds the thing up with a factor of about
30. (2 to 3.6, in a "real world" university practicum
exercise of 900 lines of code)
Even given the fact that they're not really doing the
same thing, this seems rather much :(
```Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/2280randomR too slow2019-07-07T19:09:20ZguestrandomR too slowrandomR is considerably slower than implementing it manually. Maybe I have not re-implemented it precisely, maybe it is just not inlined.
```
module Main (main) where
import System.Random (RandomGen(..), randomR, )
import qualified Data.ByteString as B
newtype KnuthRandomGen = KnuthRandomGen Int
{-# INLINE knuthFactor #-}
knuthFactor :: Int
knuthFactor = 40692
{-# INLINE knuthModulus #-}
knuthModulus :: Int
knuthModulus = 2^(31::Int)-249
-- we have to split the 32 bit integer in order to avoid overflow on multiplication
knuthSplit :: Int
knuthSplit = succ $ div knuthModulus knuthFactor
knuthSplitRem :: Int
knuthSplitRem = knuthSplit * knuthFactor - knuthModulus
instance RandomGen KnuthRandomGen where
{-# INLINE next #-}
next (KnuthRandomGen s) =
-- efficient computation of @mod (s*knuthFactor) knuthModulus@ without Integer
let (sHigh, sLow) = divMod s knuthSplit
in (s, KnuthRandomGen $ flip mod knuthModulus $
knuthSplitRem*sHigh + knuthFactor*sLow)
{-# INLINE split #-}
split (KnuthRandomGen s) =
(KnuthRandomGen (s*s), KnuthRandomGen (13+s))
{-# INLINE genRange #-}
genRange _ = (1, pred knuthModulus)
main :: IO ()
main =
do
-- for comparison: that's very fast
putStrLn "constant"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0@(KnuthRandomGen s) -> Just (fromIntegral s, g0))
(KnuthRandomGen 1)
-- 3 seconds on my machine
putStrLn "immediate"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0 -> let (w,g1) = next g0
in Just (fromIntegral (mod w 256), g1))
(KnuthRandomGen 1)
-- 10 seconds on my machine
putStrLn "randomR"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0 -> Just (let (w,g1) = randomR (0,255) g0
in (fromIntegral (w::Int), g1)))
(KnuthRandomGen 1)
{-
ghc -o dist/build/randomtest -O -Wall -package bytestring-0.9.0.5 -ddump-simpl-iterations speedtest/RandomTest.hs
-}
{-
bytestring-0.9.0.1 as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN
-}
```
Is this related to Ticket 427?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------------- |
| Version | 6.8.2 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | ghc@henning-thielemann.de |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"randomR too slow","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.8.2","keywords":["randomR"],"differentials":[],"test_case":"","architecture":"","cc":["ghc@henning-thielemann.de"],"type":"Bug","description":"randomR is considerably slower than implementing it manually. Maybe I have not re-implemented it precisely, maybe it is just not inlined.\r\n\r\n{{{\r\nmodule Main (main) where\r\n\r\nimport System.Random (RandomGen(..), randomR, )\r\nimport qualified Data.ByteString as B\r\n\r\nnewtype KnuthRandomGen = KnuthRandomGen Int\r\n\r\n{-# INLINE knuthFactor #-}\r\nknuthFactor :: Int\r\nknuthFactor = 40692\r\n\r\n{-# INLINE knuthModulus #-}\r\nknuthModulus :: Int\r\nknuthModulus = 2^(31::Int)-249\r\n\r\n-- we have to split the 32 bit integer in order to avoid overflow on multiplication\r\nknuthSplit :: Int\r\nknuthSplit = succ $ div knuthModulus knuthFactor\r\n\r\nknuthSplitRem :: Int\r\nknuthSplitRem = knuthSplit * knuthFactor - knuthModulus\r\n\r\ninstance RandomGen KnuthRandomGen where\r\n {-# INLINE next #-}\r\n next (KnuthRandomGen s) =\r\n -- efficient computation of @mod (s*knuthFactor) knuthModulus@ without Integer\r\n let (sHigh, sLow) = divMod s knuthSplit\r\n in (s, KnuthRandomGen $ flip mod knuthModulus $\r\n knuthSplitRem*sHigh + knuthFactor*sLow)\r\n {-# INLINE split #-}\r\n split (KnuthRandomGen s) =\r\n (KnuthRandomGen (s*s), KnuthRandomGen (13+s))\r\n {-# INLINE genRange #-}\r\n genRange _ = (1, pred knuthModulus)\r\n\r\n\r\nmain :: IO ()\r\nmain =\r\n do \r\n -- for comparison: that's very fast\r\n putStrLn \"constant\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0@(KnuthRandomGen s) -> Just (fromIntegral s, g0))\r\n (KnuthRandomGen 1)\r\n\r\n -- 3 seconds on my machine\r\n putStrLn \"immediate\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0 -> let (w,g1) = next g0\r\n in Just (fromIntegral (mod w 256), g1))\r\n (KnuthRandomGen 1)\r\n\r\n -- 10 seconds on my machine\r\n putStrLn \"randomR\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0 -> Just (let (w,g1) = randomR (0,255) g0\r\n in (fromIntegral (w::Int), g1)))\r\n (KnuthRandomGen 1)\r\n\r\n\r\n{-\r\nghc -o dist/build/randomtest -O -Wall -package bytestring-0.9.0.5 -ddump-simpl-iterations speedtest/RandomTest.hs\r\n-}\r\n{-\r\nbytestring-0.9.0.1 as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN\r\n-}\r\n\r\n}}}\r\n\r\nIs this related to Ticket 427?\r\n","type_of_failure":"OtherFailure","blocking":[]} -->randomR is considerably slower than implementing it manually. Maybe I have not re-implemented it precisely, maybe it is just not inlined.
```
module Main (main) where
import System.Random (RandomGen(..), randomR, )
import qualified Data.ByteString as B
newtype KnuthRandomGen = KnuthRandomGen Int
{-# INLINE knuthFactor #-}
knuthFactor :: Int
knuthFactor = 40692
{-# INLINE knuthModulus #-}
knuthModulus :: Int
knuthModulus = 2^(31::Int)-249
-- we have to split the 32 bit integer in order to avoid overflow on multiplication
knuthSplit :: Int
knuthSplit = succ $ div knuthModulus knuthFactor
knuthSplitRem :: Int
knuthSplitRem = knuthSplit * knuthFactor - knuthModulus
instance RandomGen KnuthRandomGen where
{-# INLINE next #-}
next (KnuthRandomGen s) =
-- efficient computation of @mod (s*knuthFactor) knuthModulus@ without Integer
let (sHigh, sLow) = divMod s knuthSplit
in (s, KnuthRandomGen $ flip mod knuthModulus $
knuthSplitRem*sHigh + knuthFactor*sLow)
{-# INLINE split #-}
split (KnuthRandomGen s) =
(KnuthRandomGen (s*s), KnuthRandomGen (13+s))
{-# INLINE genRange #-}
genRange _ = (1, pred knuthModulus)
main :: IO ()
main =
do
-- for comparison: that's very fast
putStrLn "constant"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0@(KnuthRandomGen s) -> Just (fromIntegral s, g0))
(KnuthRandomGen 1)
-- 3 seconds on my machine
putStrLn "immediate"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0 -> let (w,g1) = next g0
in Just (fromIntegral (mod w 256), g1))
(KnuthRandomGen 1)
-- 10 seconds on my machine
putStrLn "randomR"
B.writeFile "random.out" $ fst $
B.unfoldrN 10000000
(\g0 -> Just (let (w,g1) = randomR (0,255) g0
in (fromIntegral (w::Int), g1)))
(KnuthRandomGen 1)
{-
ghc -o dist/build/randomtest -O -Wall -package bytestring-0.9.0.5 -ddump-simpl-iterations speedtest/RandomTest.hs
-}
{-
bytestring-0.9.0.1 as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN
-}
```
Is this related to Ticket 427?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------------- |
| Version | 6.8.2 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | ghc@henning-thielemann.de |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"randomR too slow","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.8.2","keywords":["randomR"],"differentials":[],"test_case":"","architecture":"","cc":["ghc@henning-thielemann.de"],"type":"Bug","description":"randomR is considerably slower than implementing it manually. Maybe I have not re-implemented it precisely, maybe it is just not inlined.\r\n\r\n{{{\r\nmodule Main (main) where\r\n\r\nimport System.Random (RandomGen(..), randomR, )\r\nimport qualified Data.ByteString as B\r\n\r\nnewtype KnuthRandomGen = KnuthRandomGen Int\r\n\r\n{-# INLINE knuthFactor #-}\r\nknuthFactor :: Int\r\nknuthFactor = 40692\r\n\r\n{-# INLINE knuthModulus #-}\r\nknuthModulus :: Int\r\nknuthModulus = 2^(31::Int)-249\r\n\r\n-- we have to split the 32 bit integer in order to avoid overflow on multiplication\r\nknuthSplit :: Int\r\nknuthSplit = succ $ div knuthModulus knuthFactor\r\n\r\nknuthSplitRem :: Int\r\nknuthSplitRem = knuthSplit * knuthFactor - knuthModulus\r\n\r\ninstance RandomGen KnuthRandomGen where\r\n {-# INLINE next #-}\r\n next (KnuthRandomGen s) =\r\n -- efficient computation of @mod (s*knuthFactor) knuthModulus@ without Integer\r\n let (sHigh, sLow) = divMod s knuthSplit\r\n in (s, KnuthRandomGen $ flip mod knuthModulus $\r\n knuthSplitRem*sHigh + knuthFactor*sLow)\r\n {-# INLINE split #-}\r\n split (KnuthRandomGen s) =\r\n (KnuthRandomGen (s*s), KnuthRandomGen (13+s))\r\n {-# INLINE genRange #-}\r\n genRange _ = (1, pred knuthModulus)\r\n\r\n\r\nmain :: IO ()\r\nmain =\r\n do \r\n -- for comparison: that's very fast\r\n putStrLn \"constant\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0@(KnuthRandomGen s) -> Just (fromIntegral s, g0))\r\n (KnuthRandomGen 1)\r\n\r\n -- 3 seconds on my machine\r\n putStrLn \"immediate\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0 -> let (w,g1) = next g0\r\n in Just (fromIntegral (mod w 256), g1))\r\n (KnuthRandomGen 1)\r\n\r\n -- 10 seconds on my machine\r\n putStrLn \"randomR\"\r\n B.writeFile \"random.out\" $ fst $\r\n B.unfoldrN 10000000\r\n (\\g0 -> Just (let (w,g1) = randomR (0,255) g0\r\n in (fromIntegral (w::Int), g1)))\r\n (KnuthRandomGen 1)\r\n\r\n\r\n{-\r\nghc -o dist/build/randomtest -O -Wall -package bytestring-0.9.0.5 -ddump-simpl-iterations speedtest/RandomTest.hs\r\n-}\r\n{-\r\nbytestring-0.9.0.1 as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN\r\n-}\r\n\r\n}}}\r\n\r\nIs this related to Ticket 427?\r\n","type_of_failure":"OtherFailure","blocking":[]} -->Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/2470read for StdGen fails for arbitrary string2019-07-07T19:08:25Zguestread for StdGen fails for arbitrary stringAccording to the docs for StdGen:
"In addition, read may be used to map an arbitrary string (not necessarily one produced by show) onto a value of type StdGen. In general, the read instance of StdGen has the following properties:
- It guarantees to succeed on any string.
- It guarantees to consume only a finite portion of the string.
- Different argument strings are likely to result in different results."
Here's what happens on my system:
C:\\odm\\ghc\\lib\>ghci
GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
Prelude\> :mod +System.Random
Prelude System.Random\> (read "tasty tofu") :: StdGen
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package random-1.0.0.0 ... linking ... done.
- \*\* Exception: Prelude.read: no parse
Prelude System.Random\>
You can contact me at orielmaxime\@yahoo.com if you need more information.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.8.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"read for StdGen fails for arbitrary string","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.8.3","keywords":["StdGen","read"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"According to the docs for StdGen:\r\n\r\n\"In addition, read may be used to map an arbitrary string (not necessarily one produced by show) onto a value of type StdGen. In general, the read instance of StdGen has the following properties:\r\n\r\n * It guarantees to succeed on any string.\r\n * It guarantees to consume only a finite portion of the string.\r\n * Different argument strings are likely to result in different results.\"\r\n\r\nHere's what happens on my system:\r\n\r\nC:\\odm\\ghc\\lib>ghci\r\nGHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help\r\nLoading package base ... linking ... done.\r\nPrelude> :mod +System.Random\r\nPrelude System.Random> (read \"tasty tofu\") :: StdGen\r\nLoading package old-locale-1.0.0.0 ... linking ... done.\r\nLoading package old-time-1.0.0.0 ... linking ... done.\r\nLoading package random-1.0.0.0 ... linking ... done.\r\n*** Exception: Prelude.read: no parse\r\nPrelude System.Random>\r\n\r\nYou can contact me at orielmaxime@yahoo.com if you need more information.","type_of_failure":"OtherFailure","blocking":[]} -->According to the docs for StdGen:
"In addition, read may be used to map an arbitrary string (not necessarily one produced by show) onto a value of type StdGen. In general, the read instance of StdGen has the following properties:
- It guarantees to succeed on any string.
- It guarantees to consume only a finite portion of the string.
- Different argument strings are likely to result in different results."
Here's what happens on my system:
C:\\odm\\ghc\\lib\>ghci
GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help
Loading package base ... linking ... done.
Prelude\> :mod +System.Random
Prelude System.Random\> (read "tasty tofu") :: StdGen
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package random-1.0.0.0 ... linking ... done.
- \*\* Exception: Prelude.read: no parse
Prelude System.Random\>
You can contact me at orielmaxime\@yahoo.com if you need more information.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.8.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"read for StdGen fails for arbitrary string","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.8.3","keywords":["StdGen","read"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"According to the docs for StdGen:\r\n\r\n\"In addition, read may be used to map an arbitrary string (not necessarily one produced by show) onto a value of type StdGen. In general, the read instance of StdGen has the following properties:\r\n\r\n * It guarantees to succeed on any string.\r\n * It guarantees to consume only a finite portion of the string.\r\n * Different argument strings are likely to result in different results.\"\r\n\r\nHere's what happens on my system:\r\n\r\nC:\\odm\\ghc\\lib>ghci\r\nGHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help\r\nLoading package base ... linking ... done.\r\nPrelude> :mod +System.Random\r\nPrelude System.Random> (read \"tasty tofu\") :: StdGen\r\nLoading package old-locale-1.0.0.0 ... linking ... done.\r\nLoading package old-time-1.0.0.0 ... linking ... done.\r\nLoading package random-1.0.0.0 ... linking ... done.\r\n*** Exception: Prelude.read: no parse\r\nPrelude System.Random>\r\n\r\nYou can contact me at orielmaxime@yahoo.com if you need more information.","type_of_failure":"OtherFailure","blocking":[]} -->https://gitlab.haskell.org/ghc/ghc/issues/3575mkStdGen and split conspire to make some programs predictable2019-07-07T19:03:18ZrwbartonmkStdGen and split conspire to make some programs predictableThe following program `random.hs` is intended to produce a line containing 30 random 0s or 1s. It is not an example of the best way to use System.Random, but it looks innocuous enough.
```
import Control.Monad
import System.Random
print0or1 = do
g <- newStdGen
putStr . show . fst $ randomR (0, 1 :: Int) g
main = replicateM_ 30 print0or1 >> putStrLn ""
```
Let's try running it a thousand times:
```
rwbarton@functor:/tmp$ ghc-6.10.1 -O2 --make random
[1 of 1] Compiling Main ( random.hs, random.o )
Linking random ...
rwbarton@functor:/tmp$ for i in `seq 1 1000` ; do ./random >> random.out ; done
rwbarton@functor:/tmp$ sort random.out | uniq | wc -l
60
```
That's odd... there are 2\^30\^ possible output lines, but when I tried to generate 1000 random ones, I only got 60 distinct outputs. Why did that happen?
One might think this is due to poor initial seeding of the random number generator (due to the time not changing very much during the test), but this is not the case. Attached is a fancier version of the program which reads an initial seed from `/dev/urandom`; it exhibits the same behavior.
This phenomenon is not too hard to explain. It is ultimately due to a poor interaction between `mkStdGen` and `split`. First, we need to know a bit about the design of System.Random (some statements simplified slightly for this discussion).
- The state of the RNG consists of two `Int32`s, `s1` and `s2`.
- The initial state produced by mkStdGen almost always has `s2` equal to 1. (Extremely rarely, it might have `s2` equal to 2. We'll ignore this as it doesn't affect the argument.)
- To generate a random 0 or 1, we first generate a new state using some simple functions `s1' = next1(s1)`, `s2' = next2(s2)`. (Note that `s1` and `s2` "evolve" independently.) The random value returned is the lowest bit of `s1'` minus `s2'`.
- Splitting the generator `(s1, s2)` yields the two generators `(s1+1, next2(s2))` and `(next1(s1), s2-1)`.
Our program functions as follows.
- Initialize the generator stored in `theStdGen` (`s1` is some varying value `a`, `s2` is 1).
- Repeatedly split the generator, replacing it with the first output, and use the second output to generate a 0 or 1.
If we watch `theStdGen` while our program runs, we will see that `s1` is incremented by 1 at each step, while `s2` follows the fixed sequence `1`, `next2(1)`, `next2(next2(1))`, etc. The 0 or 1 we output at the `k`th step is thus the lowest bit of `next1(next1(a+k-1))` minus `b`,,k,,, where `b`,,k,, is some fixed sequence. And as `k` varies, `next1(next1(a+k-1))` turns out to be just an arithmetic sequence with fixed difference modulo a fixed prime so its lowest bits are extremely predictable even without knowing `a`.
This issue can be fixed to some extent, without breaking backwards compatibility, by adding another method (besides `mkStdGen`) to create a generator, which does not have predictable `s2`, and using it to initialize the system RNG.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.10.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"mkStdGen and split conspire to make some programs predictable","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.10.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The following program `random.hs` is intended to produce a line containing 30 random 0s or 1s. It is not an example of the best way to use System.Random, but it looks innocuous enough.\r\n\r\n{{{\r\nimport Control.Monad\r\nimport System.Random\r\n\r\nprint0or1 = do\r\n g <- newStdGen\r\n putStr . show . fst $ randomR (0, 1 :: Int) g\r\n\r\nmain = replicateM_ 30 print0or1 >> putStrLn \"\"\r\n}}}\r\n\r\nLet's try running it a thousand times:\r\n\r\n{{{\r\nrwbarton@functor:/tmp$ ghc-6.10.1 -O2 --make random\r\n[1 of 1] Compiling Main ( random.hs, random.o )\r\nLinking random ...\r\nrwbarton@functor:/tmp$ for i in `seq 1 1000` ; do ./random >> random.out ; done\r\nrwbarton@functor:/tmp$ sort random.out | uniq | wc -l\r\n60\r\n}}}\r\n\r\nThat's odd... there are 2^30^ possible output lines, but when I tried to generate 1000 random ones, I only got 60 distinct outputs. Why did that happen?\r\n\r\nOne might think this is due to poor initial seeding of the random number generator (due to the time not changing very much during the test), but this is not the case. Attached is a fancier version of the program which reads an initial seed from `/dev/urandom`; it exhibits the same behavior.\r\n\r\nThis phenomenon is not too hard to explain. It is ultimately due to a poor interaction between `mkStdGen` and `split`. First, we need to know a bit about the design of System.Random (some statements simplified slightly for this discussion).\r\n\r\n * The state of the RNG consists of two `Int32`s, `s1` and `s2`.\r\n\r\n * The initial state produced by mkStdGen almost always has `s2` equal to 1. (Extremely rarely, it might have `s2` equal to 2. We'll ignore this as it doesn't affect the argument.)\r\n\r\n * To generate a random 0 or 1, we first generate a new state using some simple functions `s1' = next1(s1)`, `s2' = next2(s2)`. (Note that `s1` and `s2` \"evolve\" independently.) The random value returned is the lowest bit of `s1'` minus `s2'`.\r\n\r\n * Splitting the generator `(s1, s2)` yields the two generators `(s1+1, next2(s2))` and `(next1(s1), s2-1)`.\r\n\r\nOur program functions as follows.\r\n\r\n * Initialize the generator stored in `theStdGen` (`s1` is some varying value `a`, `s2` is 1).\r\n\r\n * Repeatedly split the generator, replacing it with the first output, and use the second output to generate a 0 or 1.\r\n\r\nIf we watch `theStdGen` while our program runs, we will see that `s1` is incremented by 1 at each step, while `s2` follows the fixed sequence `1`, `next2(1)`, `next2(next2(1))`, etc. The 0 or 1 we output at the `k`th step is thus the lowest bit of `next1(next1(a+k-1))` minus `b`,,k,,, where `b`,,k,, is some fixed sequence. And as `k` varies, `next1(next1(a+k-1))` turns out to be just an arithmetic sequence with fixed difference modulo a fixed prime so its lowest bits are extremely predictable even without knowing `a`.\r\n\r\nThis issue can be fixed to some extent, without breaking backwards compatibility, by adding another method (besides `mkStdGen`) to create a generator, which does not have predictable `s2`, and using it to initialize the system RNG.","type_of_failure":"OtherFailure","blocking":[]} -->The following program `random.hs` is intended to produce a line containing 30 random 0s or 1s. It is not an example of the best way to use System.Random, but it looks innocuous enough.
```
import Control.Monad
import System.Random
print0or1 = do
g <- newStdGen
putStr . show . fst $ randomR (0, 1 :: Int) g
main = replicateM_ 30 print0or1 >> putStrLn ""
```
Let's try running it a thousand times:
```
rwbarton@functor:/tmp$ ghc-6.10.1 -O2 --make random
[1 of 1] Compiling Main ( random.hs, random.o )
Linking random ...
rwbarton@functor:/tmp$ for i in `seq 1 1000` ; do ./random >> random.out ; done
rwbarton@functor:/tmp$ sort random.out | uniq | wc -l
60
```
That's odd... there are 2\^30\^ possible output lines, but when I tried to generate 1000 random ones, I only got 60 distinct outputs. Why did that happen?
One might think this is due to poor initial seeding of the random number generator (due to the time not changing very much during the test), but this is not the case. Attached is a fancier version of the program which reads an initial seed from `/dev/urandom`; it exhibits the same behavior.
This phenomenon is not too hard to explain. It is ultimately due to a poor interaction between `mkStdGen` and `split`. First, we need to know a bit about the design of System.Random (some statements simplified slightly for this discussion).
- The state of the RNG consists of two `Int32`s, `s1` and `s2`.
- The initial state produced by mkStdGen almost always has `s2` equal to 1. (Extremely rarely, it might have `s2` equal to 2. We'll ignore this as it doesn't affect the argument.)
- To generate a random 0 or 1, we first generate a new state using some simple functions `s1' = next1(s1)`, `s2' = next2(s2)`. (Note that `s1` and `s2` "evolve" independently.) The random value returned is the lowest bit of `s1'` minus `s2'`.
- Splitting the generator `(s1, s2)` yields the two generators `(s1+1, next2(s2))` and `(next1(s1), s2-1)`.
Our program functions as follows.
- Initialize the generator stored in `theStdGen` (`s1` is some varying value `a`, `s2` is 1).
- Repeatedly split the generator, replacing it with the first output, and use the second output to generate a 0 or 1.
If we watch `theStdGen` while our program runs, we will see that `s1` is incremented by 1 at each step, while `s2` follows the fixed sequence `1`, `next2(1)`, `next2(next2(1))`, etc. The 0 or 1 we output at the `k`th step is thus the lowest bit of `next1(next1(a+k-1))` minus `b`,,k,,, where `b`,,k,, is some fixed sequence. And as `k` varies, `next1(next1(a+k-1))` turns out to be just an arithmetic sequence with fixed difference modulo a fixed prime so its lowest bits are extremely predictable even without knowing `a`.
This issue can be fixed to some extent, without breaking backwards compatibility, by adding another method (besides `mkStdGen`) to create a generator, which does not have predictable `s2`, and using it to initialize the system RNG.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.10.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"mkStdGen and split conspire to make some programs predictable","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.10.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The following program `random.hs` is intended to produce a line containing 30 random 0s or 1s. It is not an example of the best way to use System.Random, but it looks innocuous enough.\r\n\r\n{{{\r\nimport Control.Monad\r\nimport System.Random\r\n\r\nprint0or1 = do\r\n g <- newStdGen\r\n putStr . show . fst $ randomR (0, 1 :: Int) g\r\n\r\nmain = replicateM_ 30 print0or1 >> putStrLn \"\"\r\n}}}\r\n\r\nLet's try running it a thousand times:\r\n\r\n{{{\r\nrwbarton@functor:/tmp$ ghc-6.10.1 -O2 --make random\r\n[1 of 1] Compiling Main ( random.hs, random.o )\r\nLinking random ...\r\nrwbarton@functor:/tmp$ for i in `seq 1 1000` ; do ./random >> random.out ; done\r\nrwbarton@functor:/tmp$ sort random.out | uniq | wc -l\r\n60\r\n}}}\r\n\r\nThat's odd... there are 2^30^ possible output lines, but when I tried to generate 1000 random ones, I only got 60 distinct outputs. Why did that happen?\r\n\r\nOne might think this is due to poor initial seeding of the random number generator (due to the time not changing very much during the test), but this is not the case. Attached is a fancier version of the program which reads an initial seed from `/dev/urandom`; it exhibits the same behavior.\r\n\r\nThis phenomenon is not too hard to explain. It is ultimately due to a poor interaction between `mkStdGen` and `split`. First, we need to know a bit about the design of System.Random (some statements simplified slightly for this discussion).\r\n\r\n * The state of the RNG consists of two `Int32`s, `s1` and `s2`.\r\n\r\n * The initial state produced by mkStdGen almost always has `s2` equal to 1. (Extremely rarely, it might have `s2` equal to 2. We'll ignore this as it doesn't affect the argument.)\r\n\r\n * To generate a random 0 or 1, we first generate a new state using some simple functions `s1' = next1(s1)`, `s2' = next2(s2)`. (Note that `s1` and `s2` \"evolve\" independently.) The random value returned is the lowest bit of `s1'` minus `s2'`.\r\n\r\n * Splitting the generator `(s1, s2)` yields the two generators `(s1+1, next2(s2))` and `(next1(s1), s2-1)`.\r\n\r\nOur program functions as follows.\r\n\r\n * Initialize the generator stored in `theStdGen` (`s1` is some varying value `a`, `s2` is 1).\r\n\r\n * Repeatedly split the generator, replacing it with the first output, and use the second output to generate a 0 or 1.\r\n\r\nIf we watch `theStdGen` while our program runs, we will see that `s1` is incremented by 1 at each step, while `s2` follows the fixed sequence `1`, `next2(1)`, `next2(next2(1))`, etc. The 0 or 1 we output at the `k`th step is thus the lowest bit of `next1(next1(a+k-1))` minus `b`,,k,,, where `b`,,k,, is some fixed sequence. And as `k` varies, `next1(next1(a+k-1))` turns out to be just an arithmetic sequence with fixed difference modulo a fixed prime so its lowest bits are extremely predictable even without knowing `a`.\r\n\r\nThis issue can be fixed to some extent, without breaking backwards compatibility, by adding another method (besides `mkStdGen`) to create a generator, which does not have predictable `s2`, and using it to initialize the system RNG.","type_of_failure":"OtherFailure","blocking":[]} -->Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/3620The seeds generated by split are not independent2019-07-07T19:03:06ZNickSmallboneThe seeds generated by split are not independentSuppose we split a seed into two like this:
```
split' :: StdGen -> (StdGen, StdGen)
split' g = (g12, g21)
where (_, g12) = split g1
(g21, _) = split g2
(g1, g2) = split g
```
Since g1 and g2 are independent, g12 and g21 ought to be too. But they're not! If we use both of g12 and g21 to generate a random number in the range \[0..10\], then the two numbers ought to be equal 1/11 of the time. In fact, they're never equal.
Here is a test program that ought to return True 1/11 of the time but
actually always returns False:
```
sample :: StdGen -> (Int, Int)
sample g = (fst (randomR (0, 10) g1),
fst (randomR (0, 10) g2))
where (g1, g2) = split' g
test :: StdGen -> Bool
test g = fst (sample g) == snd (sample g)
```
I attached a program that prints the distribution of values from
`test` for other ranges than \[0..10\]. The distribution is
always quite bad no matter what the range is.
The upshot of all this is that the following QuickCheck (version 2)
property always passes, even though it's false:
```
import Test.QuickCheck
import Text.Show.Functions
newtype Eleven = Eleven Int deriving Eq
instance Arbitrary Eleven where
arbitrary = fmap Eleven (choose (0, 10))
prop :: (Int -> Eleven) -> Bool
prop f = f 5 /= f 6
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.11 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"The seeds generated by split are not independent","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.11","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Suppose we split a seed into two like this:\r\n{{{\r\nsplit' :: StdGen -> (StdGen, StdGen)\r\nsplit' g = (g12, g21)\r\n where (_, g12) = split g1\r\n (g21, _) = split g2\r\n (g1, g2) = split g\r\n}}}\r\nSince g1 and g2 are independent, g12 and g21 ought to be too. But they're not! If we use both of g12 and g21 to generate a random number in the range [0..10], then the two numbers ought to be equal 1/11 of the time. In fact, they're never equal.\r\nHere is a test program that ought to return True 1/11 of the time but\r\nactually always returns False:\r\n{{{\r\nsample :: StdGen -> (Int, Int)\r\nsample g = (fst (randomR (0, 10) g1),\r\n fst (randomR (0, 10) g2))\r\n where (g1, g2) = split' g\r\ntest :: StdGen -> Bool\r\ntest g = fst (sample g) == snd (sample g)\r\n}}}\r\n\r\nI attached a program that prints the distribution of values from\r\n{{{test}}} for other ranges than [0..10]. The distribution is\r\nalways quite bad no matter what the range is.\r\n\r\nThe upshot of all this is that the following QuickCheck (version 2)\r\nproperty always passes, even though it's false:\r\n{{{\r\nimport Test.QuickCheck\r\nimport Text.Show.Functions\r\n\r\nnewtype Eleven = Eleven Int deriving Eq\r\n\r\ninstance Arbitrary Eleven where\r\n arbitrary = fmap Eleven (choose (0, 10))\r\n\r\nprop :: (Int -> Eleven) -> Bool\r\nprop f = f 5 /= f 6\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->Suppose we split a seed into two like this:
```
split' :: StdGen -> (StdGen, StdGen)
split' g = (g12, g21)
where (_, g12) = split g1
(g21, _) = split g2
(g1, g2) = split g
```
Since g1 and g2 are independent, g12 and g21 ought to be too. But they're not! If we use both of g12 and g21 to generate a random number in the range \[0..10\], then the two numbers ought to be equal 1/11 of the time. In fact, they're never equal.
Here is a test program that ought to return True 1/11 of the time but
actually always returns False:
```
sample :: StdGen -> (Int, Int)
sample g = (fst (randomR (0, 10) g1),
fst (randomR (0, 10) g2))
where (g1, g2) = split' g
test :: StdGen -> Bool
test g = fst (sample g) == snd (sample g)
```
I attached a program that prints the distribution of values from
`test` for other ranges than \[0..10\]. The distribution is
always quite bad no matter what the range is.
The upshot of all this is that the following QuickCheck (version 2)
property always passes, even though it's false:
```
import Test.QuickCheck
import Text.Show.Functions
newtype Eleven = Eleven Int deriving Eq
instance Arbitrary Eleven where
arbitrary = fmap Eleven (choose (0, 10))
prop :: (Int -> Eleven) -> Bool
prop f = f 5 /= f 6
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.11 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"The seeds generated by split are not independent","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.11","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Suppose we split a seed into two like this:\r\n{{{\r\nsplit' :: StdGen -> (StdGen, StdGen)\r\nsplit' g = (g12, g21)\r\n where (_, g12) = split g1\r\n (g21, _) = split g2\r\n (g1, g2) = split g\r\n}}}\r\nSince g1 and g2 are independent, g12 and g21 ought to be too. But they're not! If we use both of g12 and g21 to generate a random number in the range [0..10], then the two numbers ought to be equal 1/11 of the time. In fact, they're never equal.\r\nHere is a test program that ought to return True 1/11 of the time but\r\nactually always returns False:\r\n{{{\r\nsample :: StdGen -> (Int, Int)\r\nsample g = (fst (randomR (0, 10) g1),\r\n fst (randomR (0, 10) g2))\r\n where (g1, g2) = split' g\r\ntest :: StdGen -> Bool\r\ntest g = fst (sample g) == snd (sample g)\r\n}}}\r\n\r\nI attached a program that prints the distribution of values from\r\n{{{test}}} for other ranges than [0..10]. The distribution is\r\nalways quite bad no matter what the range is.\r\n\r\nThe upshot of all this is that the following QuickCheck (version 2)\r\nproperty always passes, even though it's false:\r\n{{{\r\nimport Test.QuickCheck\r\nimport Text.Show.Functions\r\n\r\nnewtype Eleven = Eleven Int deriving Eq\r\n\r\ninstance Arbitrary Eleven where\r\n arbitrary = fmap Eleven (choose (0, 10))\r\n\r\nprop :: (Int -> Eleven) -> Bool\r\nprop f = f 5 /= f 6\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/3982Random instance for Double can generate values out of requested range2019-07-07T19:01:16ZmokusRandom instance for Double can generate values out of requested rangeThere appears to be an off-by-one error in randomIvalDouble, causing it to return values outside the requested range one time out of every few billion (exact frequency depending on the bounds of Int):
```
Prelude Control.Monad System.Random> (filter (<= 0) . randomRs (0,1)) `fmap` newStdGen :: IO [Double]
Loading package random-1.0.0.2 ... linking ... done.
[-1.1641532182693481e-10,-1.1641532182693481e-10^CInterrupted.
```
The problem appears to arise because int32Range does not represent the number of possible Int32's returned by the call to randomIvalInteger. Changing the division by int32Range in the definition of scaled_x to division by (int32Range + 1) should fix it. Attached is a darcs patch implementing this change. I don't actually know whether the resulting code reflects the intent of the interface, however. This version will produce the lower bound but not the upper bound.
Additionally, with or without the attached patch the basic structure of the scaling (adding a scaled Int32 to the midpoint of the range) does not play well with floating-point math in the first place: for example, randomR (exp 1, pi :: Double) can return a value one ULP less than 'exp 1'. This could probably be avoided by sampling a Word32 instead of an Int32 and adding the corresponding fraction of the range size to the lower bound.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Random instance for Double can generate values out of requested range","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"There appears to be an off-by-one error in randomIvalDouble, causing it to return values outside the requested range one time out of every few billion (exact frequency depending on the bounds of Int):\r\n\r\n\r\n{{{\r\nPrelude Control.Monad System.Random> (filter (<= 0) . randomRs (0,1)) `fmap` newStdGen :: IO [Double]\r\nLoading package random-1.0.0.2 ... linking ... done.\r\n[-1.1641532182693481e-10,-1.1641532182693481e-10^CInterrupted.\r\n\r\n}}}\r\n\r\nThe problem appears to arise because int32Range does not represent the number of possible Int32's returned by the call to randomIvalInteger. Changing the division by int32Range in the definition of scaled_x to division by (int32Range + 1) should fix it. Attached is a darcs patch implementing this change. I don't actually know whether the resulting code reflects the intent of the interface, however. This version will produce the lower bound but not the upper bound.\r\n\r\nAdditionally, with or without the attached patch the basic structure of the scaling (adding a scaled Int32 to the midpoint of the range) does not play well with floating-point math in the first place: for example, randomR (exp 1, pi :: Double) can return a value one ULP less than 'exp 1'. This could probably be avoided by sampling a Word32 instead of an Int32 and adding the corresponding fraction of the range size to the lower bound.","type_of_failure":"OtherFailure","blocking":[]} -->There appears to be an off-by-one error in randomIvalDouble, causing it to return values outside the requested range one time out of every few billion (exact frequency depending on the bounds of Int):
```
Prelude Control.Monad System.Random> (filter (<= 0) . randomRs (0,1)) `fmap` newStdGen :: IO [Double]
Loading package random-1.0.0.2 ... linking ... done.
[-1.1641532182693481e-10,-1.1641532182693481e-10^CInterrupted.
```
The problem appears to arise because int32Range does not represent the number of possible Int32's returned by the call to randomIvalInteger. Changing the division by int32Range in the definition of scaled_x to division by (int32Range + 1) should fix it. Attached is a darcs patch implementing this change. I don't actually know whether the resulting code reflects the intent of the interface, however. This version will produce the lower bound but not the upper bound.
Additionally, with or without the attached patch the basic structure of the scaling (adding a scaled Int32 to the midpoint of the range) does not play well with floating-point math in the first place: for example, randomR (exp 1, pi :: Double) can return a value one ULP less than 'exp 1'. This could probably be avoided by sampling a Word32 instead of an Int32 and adding the corresponding fraction of the range size to the lower bound.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Random instance for Double can generate values out of requested range","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"There appears to be an off-by-one error in randomIvalDouble, causing it to return values outside the requested range one time out of every few billion (exact frequency depending on the bounds of Int):\r\n\r\n\r\n{{{\r\nPrelude Control.Monad System.Random> (filter (<= 0) . randomRs (0,1)) `fmap` newStdGen :: IO [Double]\r\nLoading package random-1.0.0.2 ... linking ... done.\r\n[-1.1641532182693481e-10,-1.1641532182693481e-10^CInterrupted.\r\n\r\n}}}\r\n\r\nThe problem appears to arise because int32Range does not represent the number of possible Int32's returned by the call to randomIvalInteger. Changing the division by int32Range in the definition of scaled_x to division by (int32Range + 1) should fix it. Attached is a darcs patch implementing this change. I don't actually know whether the resulting code reflects the intent of the interface, however. This version will produce the lower bound but not the upper bound.\r\n\r\nAdditionally, with or without the attached patch the basic structure of the scaling (adding a scaled Int32 to the midpoint of the range) does not play well with floating-point math in the first place: for example, randomR (exp 1, pi :: Double) can return a value one ULP less than 'exp 1'. This could probably be avoided by sampling a Word32 instead of an Int32 and adding the corresponding fraction of the range size to the lower bound.","type_of_failure":"OtherFailure","blocking":[]} -->Ian Lynagh <igloo@earth.li>Ian Lynagh <igloo@earth.li>https://gitlab.haskell.org/ghc/ghc/issues/4218System.Random is way too lazy2019-07-07T19:00:04ZEyalLotemSystem.Random is way too lazyrandomRs is too lazy, generates lists of large lazy-state thunks, rather than lists of strict values.
Test program is attached.
Also, randomIO is too lazy, and builds up huge thunks. Using (randomIO \>\>= evaluate) is fine, however.
Fails with stack overflow:
```
rs <- replicateM 1000000 evaluate :: IO [Int]
print $ last rs
```
Works:
```
rs <- replicateM 1000000 (evaluate =<< randomIO) :: IO [Int]
print $ last rs
```randomRs is too lazy, generates lists of large lazy-state thunks, rather than lists of strict values.
Test program is attached.
Also, randomIO is too lazy, and builds up huge thunks. Using (randomIO \>\>= evaluate) is fine, however.
Fails with stack overflow:
```
rs <- replicateM 1000000 evaluate :: IO [Int]
print $ last rs
```
Works:
```
rs <- replicateM 1000000 (evaluate =<< randomIO) :: IO [Int]
print $ last rs
```7.10.1https://gitlab.haskell.org/ghc/ghc/issues/4314Move 'split' from the 'RandomGen' class to a new 'SplittableGen' class2019-07-07T18:59:34ZThomas Main DuBuissonMove 'split' from the 'RandomGen' class to a new 'SplittableGen' classThe proposal is to:
1) Create the 'SplittableGen' class in System.Random:
class SplittableGen g where split :: g -\> (g,g)
2) (Re)move the 'split' routine from RandomGen.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Move 'split' from the 'RandomGen' class to a new 'SplittableGen' class","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The proposal is to:\r\n\r\n1) Create the 'SplittableGen' class in System.Random:\r\nclass SplittableGen g where split :: g -> (g,g)\r\n\r\n2) (Re)move the 'split' routine from RandomGen.","type_of_failure":"OtherFailure","blocking":[]} -->The proposal is to:
1) Create the 'SplittableGen' class in System.Random:
class SplittableGen g where split :: g -\> (g,g)
2) (Re)move the 'split' routine from RandomGen.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Move 'split' from the 'RandomGen' class to a new 'SplittableGen' class","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The proposal is to:\r\n\r\n1) Create the 'SplittableGen' class in System.Random:\r\nclass SplittableGen g where split :: g -> (g,g)\r\n\r\n2) (Re)move the 'split' routine from RandomGen.","type_of_failure":"OtherFailure","blocking":[]} -->Not GHChttps://gitlab.haskell.org/ghc/ghc/issues/4315Generalize the 'RandomGen' and 'Random' classes2019-07-07T18:59:33ZThomas Main DuBuissonGeneralize the 'RandomGen' and 'Random' classesRandomGen and Random classes assume generators produce Int values. This is non-ideal as many high speed generators produce special values (ex: doubles) or generic values (bit streams / bytestrings) that can be converted directly to my types easier than coercing to Int then to an 'a' via the Random class.
The proposal is to change the classes from/to:
```
class RandomGen g where
-->
class RandomGen g v | g -> v where
```
and
```
class Random a where
-->
class Random a v where
```
And make needed changes to the classes instances that follow from these.RandomGen and Random classes assume generators produce Int values. This is non-ideal as many high speed generators produce special values (ex: doubles) or generic values (bit streams / bytestrings) that can be converted directly to my types easier than coercing to Int then to an 'a' via the Random class.
The proposal is to change the classes from/to:
```
class RandomGen g where
-->
class RandomGen g v | g -> v where
```
and
```
class Random a where
-->
class Random a v where
```
And make needed changes to the classes instances that follow from these.Not GHChttps://gitlab.haskell.org/ghc/ghc/issues/4379Add Random instances for more base types2019-07-07T18:59:16ZbasvandijkAdd Random instances for more base typesProposal:
Add `Random` instances for:
- all the types in `Data.Int`:
(`Int` is already provided)
> `Int8`,
> `Int16`,
> `Int32`,
> `Int64`
- all the types in `Data.Word`:
`Word`,
> `Word8`,
> `Word16`,
> `Word32`,
> `Word64`
- almost all the types in `Foreign.C.Types`:
`CChar`,
> `CSChar`,
> `CUChar`,
> `CShort`,
> `CUShort`,
> `CInt`,
> `CUInt`,
> `CLong`,
> `CULong`,
> `CPtrdiff`,
> `CSize`,
> `CWchar`
> `CSigAtomic`,
> `CLLong`,
> `CULLong`,
> `CIntPtr`,
> `CUIntPtr`,
> `CIntMax`,
> `CUIntMax`,
> `CFloat`,
> `CDouble`
Does it make sense to have `Random` instances for `CClock` and `CTime`?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Add Random instances for more base types","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Proposal: \r\n\r\nAdd `Random` instances for:\r\n\r\n * all the types in `Data.Int`:\r\n (`Int` is already provided) \r\n `Int8`, \r\n `Int16`, \r\n `Int32`, \r\n `Int64` \r\n\r\n * all the types in `Data.Word`: \r\n `Word`, \r\n `Word8`, \r\n `Word16`, \r\n `Word32`, \r\n `Word64`\r\n\r\n * almost all the types in `Foreign.C.Types`: \r\n `CChar`, \r\n `CSChar`, \r\n `CUChar`, \r\n `CShort`, \r\n `CUShort`, \r\n `CInt`, \r\n `CUInt`, \r\n `CLong`, \r\n `CULong`, \r\n `CPtrdiff`, \r\n `CSize`, \r\n `CWchar` \r\n `CSigAtomic`,\r\n `CLLong`, \r\n `CULLong`, \r\n `CIntPtr`, \r\n `CUIntPtr`, \r\n `CIntMax`, \r\n `CUIntMax`,\r\n `CFloat`,\r\n `CDouble`\r\n\r\nDoes it make sense to have `Random` instances for `CClock` and `CTime`?","type_of_failure":"OtherFailure","blocking":[]} -->Proposal:
Add `Random` instances for:
- all the types in `Data.Int`:
(`Int` is already provided)
> `Int8`,
> `Int16`,
> `Int32`,
> `Int64`
- all the types in `Data.Word`:
`Word`,
> `Word8`,
> `Word16`,
> `Word32`,
> `Word64`
- almost all the types in `Foreign.C.Types`:
`CChar`,
> `CSChar`,
> `CUChar`,
> `CShort`,
> `CUShort`,
> `CInt`,
> `CUInt`,
> `CLong`,
> `CULong`,
> `CPtrdiff`,
> `CSize`,
> `CWchar`
> `CSigAtomic`,
> `CLLong`,
> `CULLong`,
> `CIntPtr`,
> `CUIntPtr`,
> `CIntMax`,
> `CUIntMax`,
> `CFloat`,
> `CDouble`
Does it make sense to have `Random` instances for `CClock` and `CTime`?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 6.12.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Add Random instances for more base types","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.12.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Proposal: \r\n\r\nAdd `Random` instances for:\r\n\r\n * all the types in `Data.Int`:\r\n (`Int` is already provided) \r\n `Int8`, \r\n `Int16`, \r\n `Int32`, \r\n `Int64` \r\n\r\n * all the types in `Data.Word`: \r\n `Word`, \r\n `Word8`, \r\n `Word16`, \r\n `Word32`, \r\n `Word64`\r\n\r\n * almost all the types in `Foreign.C.Types`: \r\n `CChar`, \r\n `CSChar`, \r\n `CUChar`, \r\n `CShort`, \r\n `CUShort`, \r\n `CInt`, \r\n `CUInt`, \r\n `CLong`, \r\n `CULong`, \r\n `CPtrdiff`, \r\n `CSize`, \r\n `CWchar` \r\n `CSigAtomic`,\r\n `CLLong`, \r\n `CULLong`, \r\n `CIntPtr`, \r\n `CUIntPtr`, \r\n `CIntMax`, \r\n `CUIntMax`,\r\n `CFloat`,\r\n `CDouble`\r\n\r\nDoes it make sense to have `Random` instances for `CClock` and `CTime`?","type_of_failure":"OtherFailure","blocking":[]} -->https://gitlab.haskell.org/ghc/ghc/issues/4910mkStdGen (-2^31) is ⊥2019-07-07T18:57:58Zion1mkStdGen (-2^31) is ⊥Quoting System/Random.hs:
```
mkStdGen32 :: Int32 -> StdGen
mkStdGen32 s
| s < 0 = mkStdGen32 (-s)
```
Alas, the fact that…
```
ghci> (minBound :: Data.Int.Int32) == negate minBound
True
```
…results in mkStdGen32 going into infinite recursion when applied to the minBound of Int32.
The proposed patch should fix the issue.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"mkStdGen (-2^31) is ⊥","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Quoting System/Random.hs:\r\n\r\n{{{\r\nmkStdGen32 :: Int32 -> StdGen\r\nmkStdGen32 s\r\n | s < 0 = mkStdGen32 (-s)\r\n}}}\r\n\r\nAlas, the fact that…\r\n\r\n{{{\r\nghci> (minBound :: Data.Int.Int32) == negate minBound\r\nTrue\r\n}}}\r\n\r\n…results in mkStdGen32 going into infinite recursion when applied to the minBound of Int32.\r\n\r\nThe proposed patch should fix the issue.","type_of_failure":"OtherFailure","blocking":[]} -->Quoting System/Random.hs:
```
mkStdGen32 :: Int32 -> StdGen
mkStdGen32 s
| s < 0 = mkStdGen32 (-s)
```
Alas, the fact that…
```
ghci> (minBound :: Data.Int.Int32) == negate minBound
True
```
…results in mkStdGen32 going into infinite recursion when applied to the minBound of Int32.
The proposed patch should fix the issue.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"mkStdGen (-2^31) is ⊥","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"Quoting System/Random.hs:\r\n\r\n{{{\r\nmkStdGen32 :: Int32 -> StdGen\r\nmkStdGen32 s\r\n | s < 0 = mkStdGen32 (-s)\r\n}}}\r\n\r\nAlas, the fact that…\r\n\r\n{{{\r\nghci> (minBound :: Data.Int.Int32) == negate minBound\r\nTrue\r\n}}}\r\n\r\n…results in mkStdGen32 going into infinite recursion when applied to the minBound of Int32.\r\n\r\nThe proposed patch should fix the issue.","type_of_failure":"OtherFailure","blocking":[]} -->https://gitlab.haskell.org/ghc/ghc/issues/5278System.Random.randomIvalInteger makes invalid assumptions about RandomGen2019-07-07T18:56:05ZrrnewtonSystem.Random.randomIvalInteger makes invalid assumptions about RandomGenThe existing API for `System.Random.RandomGen` allows a random number generator (RNG) to produce Ints within an arbitrary range specified by `genRange`.
For example, the following `RandomGen` produces only zeros and ones, but should be legitimate:
```
import System.Random
data BinRNG = BinRNG StdGen
instance RandomGen BinRNG where
next (BinRNG g) = (x `mod` 2, BinRNG g')
where (x,g') = next g
split (BinRNG g) = (BinRNG g1, BinRNG g2)
where (g1,g2) = split g
genRange _ = (0,1)
ls :: [Int]
ls = randoms (BinRNG$ mkStdGen 38388)
main = print $ take 20 ls
```
But `System.Random.randomIvalInteger` makes invalid assumptions about the amount of randomness produced by `next`. (Specifically, assuming that it creates the same amount as `StdGen`.) Thus, the above program will create an output with only a couple of unique ints (rather than 2\^64).
For example:
```
[4611734781337924537,4611734781337924537,-9223323645458902796,
-9223323645458902797,4611734783485408099,4611734783485408098,
-9223323645458902796,-9223323647606386357,4611734781337924538,
-9223323645458902796,-9223323645458902797,
-9223323647606386357,4611734783485408098,4611734783485408098,
-9223323647606386357,4611734781337924538,4611734781337924537,
-9223323645458902796,4611734783485408099,4611734781337924538]
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"System.Random.randomIvalInteger makes invalid assumptions about RandomGen","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"rrnewton"},"version":"7.0.3","keywords":["assumption","incorrect"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The existing API for `System.Random.RandomGen` allows a random number generator (RNG) to produce Ints within an arbitrary range specified by `genRange`. \r\n\r\nFor example, the following `RandomGen` produces only zeros and ones, but should be legitimate:\r\n\r\n{{{\r\nimport System.Random\r\n\r\ndata BinRNG = BinRNG StdGen\r\ninstance RandomGen BinRNG where \r\n next (BinRNG g) = (x `mod` 2, BinRNG g')\r\n where (x,g') = next g\r\n split (BinRNG g) = (BinRNG g1, BinRNG g2)\r\n where (g1,g2) = split g\r\n genRange _ = (0,1)\r\n\r\nls :: [Int]\r\nls = randoms (BinRNG$ mkStdGen 38388)\r\n\r\nmain = print $ take 20 ls\r\n}}}\r\n\r\nBut `System.Random.randomIvalInteger` makes invalid assumptions about the amount of randomness produced by `next`. (Specifically, assuming that it creates the same amount as `StdGen`.) Thus, the above program will create an output with only a couple of unique ints (rather than 2^64). \r\n\r\nFor example:\r\n\r\n{{{\r\n[4611734781337924537,4611734781337924537,-9223323645458902796,\r\n-9223323645458902797,4611734783485408099,4611734783485408098,\r\n-9223323645458902796,-9223323647606386357,4611734781337924538,\r\n-9223323645458902796,-9223323645458902797,\r\n-9223323647606386357,4611734783485408098,4611734783485408098,\r\n-9223323647606386357,4611734781337924538,4611734781337924537,\r\n-9223323645458902796,4611734783485408099,4611734781337924538]\r\n}}}\r\n","type_of_failure":"OtherFailure","blocking":[]} -->The existing API for `System.Random.RandomGen` allows a random number generator (RNG) to produce Ints within an arbitrary range specified by `genRange`.
For example, the following `RandomGen` produces only zeros and ones, but should be legitimate:
```
import System.Random
data BinRNG = BinRNG StdGen
instance RandomGen BinRNG where
next (BinRNG g) = (x `mod` 2, BinRNG g')
where (x,g') = next g
split (BinRNG g) = (BinRNG g1, BinRNG g2)
where (g1,g2) = split g
genRange _ = (0,1)
ls :: [Int]
ls = randoms (BinRNG$ mkStdGen 38388)
main = print $ take 20 ls
```
But `System.Random.randomIvalInteger` makes invalid assumptions about the amount of randomness produced by `next`. (Specifically, assuming that it creates the same amount as `StdGen`.) Thus, the above program will create an output with only a couple of unique ints (rather than 2\^64).
For example:
```
[4611734781337924537,4611734781337924537,-9223323645458902796,
-9223323645458902797,4611734783485408099,4611734783485408098,
-9223323645458902796,-9223323647606386357,4611734781337924538,
-9223323645458902796,-9223323645458902797,
-9223323647606386357,4611734783485408098,4611734783485408098,
-9223323647606386357,4611734781337924538,4611734781337924537,
-9223323645458902796,4611734783485408099,4611734781337924538]
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"System.Random.randomIvalInteger makes invalid assumptions about RandomGen","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"rrnewton"},"version":"7.0.3","keywords":["assumption","incorrect"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The existing API for `System.Random.RandomGen` allows a random number generator (RNG) to produce Ints within an arbitrary range specified by `genRange`. \r\n\r\nFor example, the following `RandomGen` produces only zeros and ones, but should be legitimate:\r\n\r\n{{{\r\nimport System.Random\r\n\r\ndata BinRNG = BinRNG StdGen\r\ninstance RandomGen BinRNG where \r\n next (BinRNG g) = (x `mod` 2, BinRNG g')\r\n where (x,g') = next g\r\n split (BinRNG g) = (BinRNG g1, BinRNG g2)\r\n where (g1,g2) = split g\r\n genRange _ = (0,1)\r\n\r\nls :: [Int]\r\nls = randoms (BinRNG$ mkStdGen 38388)\r\n\r\nmain = print $ take 20 ls\r\n}}}\r\n\r\nBut `System.Random.randomIvalInteger` makes invalid assumptions about the amount of randomness produced by `next`. (Specifically, assuming that it creates the same amount as `StdGen`.) Thus, the above program will create an output with only a couple of unique ints (rather than 2^64). \r\n\r\nFor example:\r\n\r\n{{{\r\n[4611734781337924537,4611734781337924537,-9223323645458902796,\r\n-9223323645458902797,4611734783485408099,4611734783485408098,\r\n-9223323645458902796,-9223323647606386357,4611734781337924538,\r\n-9223323645458902796,-9223323645458902797,\r\n-9223323647606386357,4611734783485408098,4611734783485408098,\r\n-9223323647606386357,4611734781337924538,4611734781337924537,\r\n-9223323645458902796,4611734783485408099,4611734781337924538]\r\n}}}\r\n","type_of_failure":"OtherFailure","blocking":[]} -->Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/5280System.Random commits (rand `mod` base) error.2019-07-07T18:56:05ZrrnewtonSystem.Random commits (rand `mod` base) error.You have probably at some point come across the C code "`rand() % base`"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine `rand()` producing numbers in say `[0,15)` and base being `10`.
In the function `System.Random.randomIvalInteger` you can see the same thing happening.
The only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.
This strategy appears to be used by GMP's mpz_urandomm function:
> http://gmplib.org/manual/Integer-Random-Numbers.html\#Integer-Random-Numbers
The file `urandomm.c` has the code.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"System.Random commits (rand `mod` base) error.","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"rrnewton"},"version":"7.0.3","keywords":["base","mod","random"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"You have probably at some point come across the C code \"{{{rand() % base}}}\"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine {{{rand()}}} producing numbers in say `[0,15)` and base being `10`.\r\n\r\nIn the function `System.Random.randomIvalInteger` you can see the same thing happening. \r\n\r\nThe only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.\r\n\r\nThis strategy appears to be used by GMP's mpz_urandomm function:\r\n\r\n http://gmplib.org/manual/Integer-Random-Numbers.html#Integer-Random-Numbers\r\n\r\nThe file `urandomm.c` has the code.\r\n","type_of_failure":"OtherFailure","blocking":[]} -->You have probably at some point come across the C code "`rand() % base`"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine `rand()` producing numbers in say `[0,15)` and base being `10`.
In the function `System.Random.randomIvalInteger` you can see the same thing happening.
The only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.
This strategy appears to be used by GMP's mpz_urandomm function:
> http://gmplib.org/manual/Integer-Random-Numbers.html\#Integer-Random-Numbers
The file `urandomm.c` has the code.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"System.Random commits (rand `mod` base) error.","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"rrnewton"},"version":"7.0.3","keywords":["base","mod","random"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"You have probably at some point come across the C code \"{{{rand() % base}}}\"'. It is very intuitive, but unfortunately creates non-uniform random numbers, which is easy to see if you imagine {{{rand()}}} producing numbers in say `[0,15)` and base being `10`.\r\n\r\nIn the function `System.Random.randomIvalInteger` you can see the same thing happening. \r\n\r\nThe only way I know how to deal with it and generate uniform integers within a range is to artificially restrict the range of the source of randomness to be a multiple of the desired base. It can be done simply by throwing out some random results.\r\n\r\nThis strategy appears to be used by GMP's mpz_urandomm function:\r\n\r\n http://gmplib.org/manual/Integer-Random-Numbers.html#Integer-Random-Numbers\r\n\r\nThe file `urandomm.c` has the code.\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1rrnewtonrrnewtonhttps://gitlab.haskell.org/ghc/ghc/issues/5501randomR overflow2019-07-07T18:54:59Zdaniel.is.fischerrandomR overflowWhen given a large range, `randomR` overflows at `Double` etc.
`randomIvalDouble` has two problems: first, the calculation of the center, `(l+h)/2` overflows if the range is located near `±Infinity`; second, and that concerns also `randomRFloating`, the scaling factor `(h-l)` overflows if the range is large enough.
Both problems can be fixed "well enough" by multiplying the bounds by 0.5 before the calculations and scaling up at the end,
```
0.5*l + 0.5*h instead of (l+h)/2
(0.5*h - 0.5*l)/(0.5*realToFrac int32Count) in randomIvalDouble
2.0*(0.5*l + coef*(0.5*h - 0.5*l)) in randomRFloating
```
These transformations can introduce a small error when a subnormal number is involved, but I think we can ignore that (no sane person would have a \[nonzero\] subnormal number as a bound, and a correct-for-all-cases transformation would be somewhat convoluted).
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.2.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"randomR overflow","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.2.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"When given a large range, `randomR` overflows at `Double` etc.\r\n\r\n`randomIvalDouble` has two problems: first, the calculation of the center, `(l+h)/2` overflows if the range is located near `±Infinity`; second, and that concerns also `randomRFloating`, the scaling factor `(h-l)` overflows if the range is large enough.\r\n\r\nBoth problems can be fixed \"well enough\" by multiplying the bounds by 0.5 before the calculations and scaling up at the end,\r\n{{{\r\n0.5*l + 0.5*h instead of (l+h)/2\r\n(0.5*h - 0.5*l)/(0.5*realToFrac int32Count) in randomIvalDouble\r\n2.0*(0.5*l + coef*(0.5*h - 0.5*l)) in randomRFloating\r\n}}}\r\nThese transformations can introduce a small error when a subnormal number is involved, but I think we can ignore that (no sane person would have a [nonzero] subnormal number as a bound, and a correct-for-all-cases transformation would be somewhat convoluted).\r\n","type_of_failure":"OtherFailure","blocking":[]} -->When given a large range, `randomR` overflows at `Double` etc.
`randomIvalDouble` has two problems: first, the calculation of the center, `(l+h)/2` overflows if the range is located near `±Infinity`; second, and that concerns also `randomRFloating`, the scaling factor `(h-l)` overflows if the range is large enough.
Both problems can be fixed "well enough" by multiplying the bounds by 0.5 before the calculations and scaling up at the end,
```
0.5*l + 0.5*h instead of (l+h)/2
(0.5*h - 0.5*l)/(0.5*realToFrac int32Count) in randomIvalDouble
2.0*(0.5*l + coef*(0.5*h - 0.5*l)) in randomRFloating
```
These transformations can introduce a small error when a subnormal number is involved, but I think we can ignore that (no sane person would have a \[nonzero\] subnormal number as a bound, and a correct-for-all-cases transformation would be somewhat convoluted).
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.2.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"randomR overflow","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.2.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"When given a large range, `randomR` overflows at `Double` etc.\r\n\r\n`randomIvalDouble` has two problems: first, the calculation of the center, `(l+h)/2` overflows if the range is located near `±Infinity`; second, and that concerns also `randomRFloating`, the scaling factor `(h-l)` overflows if the range is large enough.\r\n\r\nBoth problems can be fixed \"well enough\" by multiplying the bounds by 0.5 before the calculations and scaling up at the end,\r\n{{{\r\n0.5*l + 0.5*h instead of (l+h)/2\r\n(0.5*h - 0.5*l)/(0.5*realToFrac int32Count) in randomIvalDouble\r\n2.0*(0.5*l + coef*(0.5*h - 0.5*l)) in randomRFloating\r\n}}}\r\nThese transformations can introduce a small error when a subnormal number is involved, but I think we can ignore that (no sane person would have a [nonzero] subnormal number as a bound, and a correct-for-all-cases transformation would be somewhat convoluted).\r\n","type_of_failure":"OtherFailure","blocking":[]} -->rrnewtonrrnewtonhttps://gitlab.haskell.org/ghc/ghc/issues/7379rangeTest test fails on Windows2019-07-07T18:50:01ZIan Lynagh <igloo@earth.li>rangeTest test fails on WindowsThe `CWchar` type on Win32 is unsigned:
```
Prelude> minBound :: Foreign.C.Types.CWchar
0
Prelude> (-100) :: Foreign.C.Types.CWchar
65436
```
This causes the `rangeTest` test to fail:
```
CWchar R:
Stderr:
rangeTest.exe: broke lower bound: 100
```
Ryan, could you take a look please?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------ |
| Version | 7.6.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | rrnewton@gmail.com |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"rangeTest test fails on Windows","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":["rrnewton@gmail.com"],"type":"Bug","description":"The `CWchar` type on Win32 is unsigned:\r\n{{{\r\nPrelude> minBound :: Foreign.C.Types.CWchar\r\n0\r\nPrelude> (-100) :: Foreign.C.Types.CWchar\r\n65436\r\n}}}\r\nThis causes the `rangeTest` test to fail:\r\n{{{\r\nCWchar R: \r\nStderr:\r\nrangeTest.exe: broke lower bound: 100\r\n}}}\r\n\r\nRyan, could you take a look please?\r\n","type_of_failure":"OtherFailure","blocking":[]} -->The `CWchar` type on Win32 is unsigned:
```
Prelude> minBound :: Foreign.C.Types.CWchar
0
Prelude> (-100) :: Foreign.C.Types.CWchar
65436
```
This causes the `rangeTest` test to fail:
```
CWchar R:
Stderr:
rangeTest.exe: broke lower bound: 100
```
Ryan, could you take a look please?
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------ |
| Version | 7.6.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | rrnewton@gmail.com |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"rangeTest test fails on Windows","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":["rrnewton@gmail.com"],"type":"Bug","description":"The `CWchar` type on Win32 is unsigned:\r\n{{{\r\nPrelude> minBound :: Foreign.C.Types.CWchar\r\n0\r\nPrelude> (-100) :: Foreign.C.Types.CWchar\r\n65436\r\n}}}\r\nThis causes the `rangeTest` test to fail:\r\n{{{\r\nCWchar R: \r\nStderr:\r\nrangeTest.exe: broke lower bound: 100\r\n}}}\r\n\r\nRyan, could you take a look please?\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1https://gitlab.haskell.org/ghc/ghc/issues/7936newStdGen leaks memory when result is not used2019-07-07T18:47:23ZryantrinklenewStdGen leaks memory when result is not usedWhen newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:
```
-- Leaks memory
main = forever newStdGen
```
When a random number produced by the result is evaluated, no leak occurs:
```
-- Does not leak memory
main = forever $ do
r <- newStdGen
evaluate $ fst $ next r
```
However, evaluating the result itself is not sufficient to eliminate the leak:
```
-- Leaks memory
main = forever $ do
r <- newStdGen
evaluate r
```
After sufficient iterations of newStdGen, subsequent use will cause a stack overflow:
```
-- Causes stack overflow
main = do
replicateM 1000000 newStdGen
r <- newStdGen
evaluate $ fst $ next r
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"newStdGen leaks memory when result is not used","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"When newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever newStdGen\r\n}}}\r\n\r\nWhen a random number produced by the result is evaluated, no leak occurs:\r\n\r\n{{{\r\n-- Does not leak memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}\r\n\r\nHowever, evaluating the result itself is not sufficient to eliminate the leak:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate r\r\n}}}\r\n\r\nAfter sufficient iterations of newStdGen, subsequent use will cause a stack overflow:\r\n\r\n{{{\r\n-- Causes stack overflow\r\nmain = do\r\n replicateM 1000000 newStdGen\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->When newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:
```
-- Leaks memory
main = forever newStdGen
```
When a random number produced by the result is evaluated, no leak occurs:
```
-- Does not leak memory
main = forever $ do
r <- newStdGen
evaluate $ fst $ next r
```
However, evaluating the result itself is not sufficient to eliminate the leak:
```
-- Leaks memory
main = forever $ do
r <- newStdGen
evaluate r
```
After sufficient iterations of newStdGen, subsequent use will cause a stack overflow:
```
-- Causes stack overflow
main = do
replicateM 1000000 newStdGen
r <- newStdGen
evaluate $ fst $ next r
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"newStdGen leaks memory when result is not used","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"When newStdGen is invoked repeatedly without making any use of the resulting StdGen values, it leaks memory, as in the following:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever newStdGen\r\n}}}\r\n\r\nWhen a random number produced by the result is evaluated, no leak occurs:\r\n\r\n{{{\r\n-- Does not leak memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}\r\n\r\nHowever, evaluating the result itself is not sufficient to eliminate the leak:\r\n\r\n{{{\r\n-- Leaks memory\r\nmain = forever $ do\r\n r <- newStdGen\r\n evaluate r\r\n}}}\r\n\r\nAfter sufficient iterations of newStdGen, subsequent use will cause a stack overflow:\r\n\r\n{{{\r\n-- Causes stack overflow\r\nmain = do\r\n replicateM 1000000 newStdGen\r\n r <- newStdGen\r\n evaluate $ fst $ next r\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1Edward KmettEdward Kmetthttps://gitlab.haskell.org/ghc/ghc/issues/8704Use GHC.Exts.build in randoms, randomRs to achieve fusion2019-07-07T18:43:53Zion1Use GHC.Exts.build in randoms, randomRs to achieve fusionrandoms, randomRs could take advantage of list fusion.
A commit is attached for consideration.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | FeatureRequest |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Use GHC.Exts.build in randoms, randomRs to achieve fusion","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":["fusion"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"FeatureRequest","description":"randoms, randomRs could take advantage of list fusion.\r\n\r\nA commit is attached for consideration.","type_of_failure":"OtherFailure","blocking":[]} -->randoms, randomRs could take advantage of list fusion.
A commit is attached for consideration.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.6.3 |
| Type | FeatureRequest |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Use GHC.Exts.build in randoms, randomRs to achieve fusion","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.3","keywords":["fusion"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"FeatureRequest","description":"randoms, randomRs could take advantage of list fusion.\r\n\r\nA commit is attached for consideration.","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1rrnewtonrrnewtonhttps://gitlab.haskell.org/ghc/ghc/issues/8898Overall improvement for randomIvalInteger2019-07-07T18:42:54ZnovadenizenOverall improvement for randomIvalIntegerThe current `randomIvalInteger` implementation uses repeated `div` operations to approximate the size of the desired random output, then generates that number of random values from the given `RandomGen`. It does not compensate for the ``mod` base` uniformity problem. It also assumes that all `RandomGen` implementations produce the same range of random values as `StdGen`.
My new implementation addresses all these correctness issues, with potentially a slight performance improvement.
Instead of performing repeated div base operations to determine the size of the desired range, this uses faster `(* base)` operations. An equivalent set of intermediate `Integer`s is generated still.
To compensate for the ``mod` base` uniformity problem, the desired range size is multiplied by the *q* factor (1000 in my code). When *k* is the desired range and *b\^n\^* is the range of numbers generated, and *d = b\^n\^ div k*, some elements will have probability *d/b\^n\^* and others will have probability *(d+1)/b\^n\^*, resulting in significant non-uniformity when *d* is very small. When you extend the generated range beyond the minimum by a factor of *q*, you are guaranteed that *d* will be at least *q*, so the non-uniformity will be much less consequential.
This implementation also works with any `RandomGen`, even ones that produce as little as a single bit of entropy per next call or have a minimum bound other than zero.The current `randomIvalInteger` implementation uses repeated `div` operations to approximate the size of the desired random output, then generates that number of random values from the given `RandomGen`. It does not compensate for the ``mod` base` uniformity problem. It also assumes that all `RandomGen` implementations produce the same range of random values as `StdGen`.
My new implementation addresses all these correctness issues, with potentially a slight performance improvement.
Instead of performing repeated div base operations to determine the size of the desired range, this uses faster `(* base)` operations. An equivalent set of intermediate `Integer`s is generated still.
To compensate for the ``mod` base` uniformity problem, the desired range size is multiplied by the *q* factor (1000 in my code). When *k* is the desired range and *b\^n\^* is the range of numbers generated, and *d = b\^n\^ div k*, some elements will have probability *d/b\^n\^* and others will have probability *(d+1)/b\^n\^*, resulting in significant non-uniformity when *d* is very small. When you extend the generated range beyond the minimum by a factor of *q*, you are guaranteed that *d* will be at least *q*, so the non-uniformity will be much less consequential.
This implementation also works with any `RandomGen`, even ones that produce as little as a single bit of entropy per next call or have a minimum bound other than zero.https://gitlab.haskell.org/ghc/ghc/issues/8899StdGen does not generate 02019-07-07T18:42:54ZnovadenizenStdGen does not generate 0`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
`
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.9 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"StdGen does not generate 0","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.9","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"`genRange` for `StdGen` returns `(0,2147483562)`. However, as far as I can tell, `StdGen` doesn't generate 0.\r\n\r\nThis 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^''.\r\n\r\n{{{#!haskell\r\nimport System.Random\r\nimport Data.Int\r\n\r\nfind0 :: StdGen -> Int64 -> Maybe Int64\r\nfind0 g0 n0 = aux g0 n0 where\r\n aux _ 0 = Nothing\r\n aux g r = let (v,g') = next g in\r\n if v == 0 then Just (n0 - r + 1)\r\n else aux g' (r-1)\r\n\r\nmain :: IO ()\r\nmain = print $ find0 (mkStdGen 1234) 200000000000\r\n }}}\r\n","type_of_failure":"OtherFailure","blocking":[]} -->`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
`
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ---------------- |
| Version | 7.9 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/random |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"StdGen does not generate 0","status":"New","operating_system":"","component":"libraries/random","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.9","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"`genRange` for `StdGen` returns `(0,2147483562)`. However, as far as I can tell, `StdGen` doesn't generate 0.\r\n\r\nThis 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^''.\r\n\r\n{{{#!haskell\r\nimport System.Random\r\nimport Data.Int\r\n\r\nfind0 :: StdGen -> Int64 -> Maybe Int64\r\nfind0 g0 n0 = aux g0 n0 where\r\n aux _ 0 = Nothing\r\n aux g r = let (v,g') = next g in\r\n if v == 0 then Just (n0 - r + 1)\r\n else aux g' (r-1)\r\n\r\nmain :: IO ()\r\nmain = print $ find0 (mkStdGen 1234) 200000000000\r\n }}}\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.10.1Edward KmettEdward Kmett