#8898 closed bug (fixed)

Overall improvement for randomIvalInteger

Reported by: novadenizen Owned by:
Priority: normal Milestone:
Component: libraries/random Version: 7.9
Keywords: Cc: rrnewton@…, core-libraries-committee@…, rrnewton
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: #5278 #5280 #1120 Differential Revisions:

Description (last modified by hvr)

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 bn is the range of numbers generated, and d = bn div k, some elements will have probability d/bn and others will have probability (d+1)/bn, 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.

Attachments (1)

randpatch (4.0 KB) - added by novadenizen 15 months ago.
new randomIvalInteger patch

Download all attachments as: .zip

Change History (6)

Changed 15 months ago by novadenizen

new randomIvalInteger patch

comment:1 Changed 15 months ago by hvr

  • Description modified (diff)

fixup wiki-markup in description

comment:2 Changed 15 months ago by simonpj

  • Cc core-libraries-committee@… added

Sounds splendid. Adopting this or otherwise is the responsibility of the Core Libraries committee (core-libraries-committee@…). I've added them to the cc.

Simon

comment:3 Changed 15 months ago by simonpj

  • Cc rrnewton@… added

... or maybe it's Ryan Newton? Adding him too.

comment:4 Changed 14 months ago by hvr

Please re-file this at random's GitHub issue tracker over at https://github.com/haskell/random/issues

comment:5 Changed 14 months ago by rrnewton

  • Cc rrnewton added
  • Resolution set to fixed
  • Status changed from new to closed

Merged!

Note: See TracTickets for help on using tickets.