Opened 4 years ago
Closed 4 years ago
#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 Rev(s): | |
Wiki Page: |
Description (last modified by )
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.
Attachments (1)
Change History (6)
Changed 4 years ago by
comment:1 Changed 4 years ago by
Description: | modified (diff) |
---|---|
Related Tickets: | 5278 5280 1120 → #5278 #5280 #1120 |
fixup wiki-markup in description
comment:2 Changed 4 years ago by
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 4 years ago by
Cc: | rrnewton@… added |
---|
... or maybe it's Ryan Newton? Adding him too.
comment:4 Changed 4 years ago by
Please re-file this at random
's GitHub issue tracker over at https://github.com/haskell/random/issues
comment:5 Changed 4 years ago by
Cc: | rrnewton added |
---|---|
Resolution: | → fixed |
Status: | new → closed |
Merged!
new randomIvalInteger patch