[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
      Resolution:                    |         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
-------------------------------------+-------------------------------------
Changes (by hvr):

 * related:  5278 5280 1120 => #5278 #5280 #1120


Old description:

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

New description:

 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 `Integer`s 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 non-
 uniformity  when ''d'' is very small.  When you extend the generated range
 beyond the minimum by a factor of ''q'', you are guaranteed that ''d''
 will be at least ''q'', so the non-uniformity 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.

--

Comment:

 fixup wiki-markup in description

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