[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:  Not GHC    
Component:  libraries/base  |        Version:  6.6        
 Severity:  normal          |     Resolution:             
 Keywords:                  |     Difficulty:  Easy (1 hr)
 Testcase:                  |   Architecture:  Multiple   
       Os:  Multiple        |  
----------------------------+-----------------------------------------------
Changes (by igloo):

  * milestone:  => Not GHC

Old description:

> 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.

New description:

 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.

Comment:

 This probably wants to go via being a proposal.

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