randomR is non-uniform for most ranges

[astrolabe]

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.

[igloo]

This probably wants to go via being a proposal.

[igloo]

This really needs someone to propose a better algorithm, so I'll close the ticket.