[GHC] #8898: Overall improvement for randomIvalInteger

[GHC]

#8898: Overall improvement for randomIvalInteger
-------------------------------------+-------------------------------------
       Reporter:  novadenizen        |             Owner:
           Type:  bug                |            Status:  new
       Priority:  normal             |         Milestone:
      Component:  libraries/random   |           Version:  7.9
       Keywords:                     |  Operating System:  Unknown/Multiple
   Architecture:  Unknown/Multiple   |   Type of failure:  Incorrect result
     Difficulty:  Easy (less than 1  |  at runtime
  hour)                              |         Test Case:
     Blocked By:                     |          Blocking:
Related Tickets:  5278 5280 1120     |
-------------------------------------+-------------------------------------
 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 Integers 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 nonuniformity  when d is
 very small.  When you extend the generated range beyond the minimum by a
 factor of q, you are guaranteeed that d will be at least q, so the
 nonuniformity 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.

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