Ticket #1120 (closed bug: wontfix)
randomR is non-uniform for most ranges
|Reported by:||astrolabe||Owned by:|
|Type of failure:||None/Unknown||Difficulty:||Easy (less than 1 hour)|
|Test Case:||Blocked By:|
Description (last modified by igloo) (diff)
If m < n, you can't convert a uniform random sample from [0,n-1] to one from [0,m-1] using mod unless m|n. For example, if m = n-1 then the getting 0 is twice as likely as getting anything else. However, this scheme is what seems to be used in this function from http://darcs.haskell.org/ghc-6.6/packages/base/System/Random.hs
randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g) randomIvalInteger (l,h) rng | l > h = randomIvalInteger (h,l) rng | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng') where k = h - l + 1 b = 2147483561 n = iLogBase b k f 0 acc g = (acc, g) f n acc g = let (x,g') = next g in f (n-1) (fromIntegral x + acc * b) g'
One possible fix is to repeatedly sample from [0,n-1] until you get a value that is in [0,floor(n/m)*m-1]. This would work practically, but is not gauranteed to terminate. You should, in my opinion, at least try a few samples before accepting one that isn't in this range.