jeudi 15 août 2019

When getting rid of modulo bias how does min = -upper_bound % upper_bound; // work? [duplicate]

In answers to this other question, the following solution is provided, curtesy of OpenBSD, rewritten for brevity,

uint32_t foo( uint32_t limit ) {
  uint32_t min = -limit % limit, r = 0;

    for(;;) {
      r = random_function();
      if ( r >= min ) break;
    }
    return r % limit;
 }

How exactly does the line uint32_t min = -limit % limit work? What I'd like to know is, is there a mathematical proof that it does indeed calculate some lower limit for the random number and adequately removes the modulo bias?




Aucun commentaire:

Enregistrer un commentaire