Overall improvement for randomIvalInteger
|Reported by:||novadenizen||Owned by:|
|Keywords:||Cc:||rrnewton@…, core-libraries-committee@…, rrnewton|
|Type of failure:||Incorrect result at runtime||Test Case:|
|Related Tickets:||#5278 #5280 #1120||Differential Rev(s):|
Description (last modified by )
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
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.
Change History (6)
comment:1 Changed 3 years ago by
|Related Tickets:||5278 5280 1120 → #5278 #5280 #1120|