Skip to main content

Timeline for answer to Why do people say there is modulo bias when using a random number generator? by user1413793

Current License: CC BY-SA 3.0

Post Revisions

26 events
when toggle format what by license comment
May 17, 2025 at 4:03 comment added Ben Personick @ArrayBolt3 when I very first responded to the OP in this comment you replied ot from 2017, I accidentally included the ">=" instead of "=" only, which is what is in the solution I submitted, it has x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) )
Oct 25, 2024 at 1:27 comment added ArrayBolt3 @BenPersonick You sure that's right? If seeking for a 3-bit value between 0 and 2 inclusive, RM=7 and N=3. In this scenario, X >= RM - ( ( ( RM % N ) + 1 ) % N ) is equivalent to X >= 7 - ( ( ( 7 % 3 ) + 1 ) % 3 ), which evaluates to X >= 5. This is incorrect, as X % N will be 0 if X is 0 or 3, it will be 1 if X is 1 or 4, and it will be 2 only if X is 2. X = 5 will be rejected by this solution, thus introducing modulo bias.
Nov 3, 2021 at 3:05 comment added chux Critcal weakness: do { ... } while (x >= (RAND_MAX - RAND_MAX % n)); is an infinite loop when n > RAND_MAX.
Nov 26, 2020 at 10:54 comment added Rodolfo Carvalho Is the use of a loop introducing room for a side-channel attack in this case?
Oct 31, 2017 at 12:08 comment added Ben Personick I posted an additional answer explaining the problem in detail and giving the example code solution.
Oct 28, 2017 at 14:58 comment added Ben Personick X >= RM - ( ( ( RM % N ) + 1 ) % N )
Oct 28, 2017 at 14:56 comment added Ben Personick I may be nitpicking, but if the goal is to reduce wasted bits we could improve this slightly for the edge condition where RAND_MAX (RM) is only 1 less than being equally divisible by N. In this scenario, no bits need to be wasted by doing X >= (RM - RM % N)) which is of little value for small values of N, but becomes of larger value for large values of N. As mentioned by Slipp D. Thompson, there is a solution which will work only when INT_MAX (IM) > RAND_MAX but breaks when they are equal. However, there is a simple solution for this we can amend the calculation X >= (RM - RM % N) as follows:
Jul 19, 2016 at 8:04 comment added Slipp D. Thompson Another way of thinking about_RAND_MAX%n == n - 1_ is (RAND_MAX + 1) % n == 0. When reading code, I tend to understand % something == 0 as “evenly divisible” more readily than other ways of calculating it. Of course, if your C++ stdlib has RAND_MAX as the same value as INT_MAX, (RAND_MAX + 1) surely wouldn't work; so Mark's calculation remains the safest implementation.
Mar 25, 2016 at 23:16 history edited Mark Amery CC BY-SA 3.0
Bring the second code example into the flow of the answer instead of having a tacked on EDIT at the end; removal factual inaccuracy (I think) about expected number of rand() calls
Mar 22, 2016 at 14:44 history edited Matthieu M. CC BY-SA 3.0
Removed useless `max`.
Mar 21, 2016 at 15:43 history edited Matthieu M. CC BY-SA 3.0
Incorporate the comment from BlueRaja into the answer regarding a more efficient loop condition, while patching the formula he gave which is unfortunately incorrect (and in contradiction with his explanation).
Mar 21, 2016 at 3:34 history edited Rob♦ CC BY-SA 3.0
Edited back in formatting improvements which were included in the broken edit which was rolled back
Mar 20, 2016 at 20:01 history edited Tunaki CC BY-SA 3.0
edited body
Mar 20, 2016 at 20:00 history rollback Tunaki
Rollback to Revision 7
S Oct 5, 2015 at 23:34 history edited Demitri CC BY-SA 3.0
Better formatting and removed awfully inefficient example solution
S Oct 5, 2015 at 23:34 history suggested Aidan Gomez CC BY-SA 3.0
Better formatting and removed awfully inefficient example solution
Oct 5, 2015 at 22:46 review Suggested edits
S Oct 5, 2015 at 23:34
S Jul 3, 2013 at 16:34 history suggested Jared Nielsen CC BY-SA 3.0
fixed code formatting and spelling
Jul 3, 2013 at 16:16 review Suggested edits
S Jul 3, 2013 at 16:34
May 7, 2013 at 18:42 history edited user283145 CC BY-SA 3.0
the question is tagged c++ - link to c++ resource
Jun 23, 2012 at 10:44 history edited Sklivvz CC BY-SA 3.0
edited body
Jun 14, 2012 at 1:26 vote accept user1413793
Jun 11, 2012 at 18:32 history edited user1413793 CC BY-SA 3.0
Changed my while loop to a do-while loop
Jun 11, 2012 at 17:51 history edited user1413793 CC BY-SA 3.0
added 4 characters in body
Jun 11, 2012 at 17:50 history edited R. Martinho Fernandes CC BY-SA 3.0
added 9 characters in body
Jun 11, 2012 at 17:44 history answered user1413793 CC BY-SA 3.0
toggle format