[GHC] #1120: randomR is non-uniform for most ranges

[GHC]

#1120: randomR is non-uniform for most ranges
-------------------------------+--------------------------------------------
    Reporter:  astrolabe       |       Owner:          
        Type:  bug             |      Status:  new     
    Priority:  normal          |   Milestone:          
   Component:  libraries/base  |     Version:  6.6     
    Severity:  normal          |    Keywords:          
  Difficulty:  Easy (1 hr)     |    Testcase:          
Architecture:  Multiple        |          Os:  Multiple
-------------------------------+--------------------------------------------
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.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1120>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler