The GNU MP function mpz_urandomm tries rejection sampling up to 80 times (MAX_URANDOMM_ITER) to find a random number which fits within the user-specified range. Each attempt I think fails with probability at most 1/2, so the probability of 80 consecutive failures is around 0.5^80, an extremely small number.

After 80 failures, it silently uses mod to bring the too large number into range, which destroys the uniformity. I think it should instead abort, because 80 consecutive failures means something deeper is going wrong, perhaps a faulty random number generator which only emits '111...'.

## No comments :

Post a Comment