Modulo bias - это проблема, которая возникает, когда наивно использует модульную операцию, чтобы получить псевдослучайные числа, меньшие, чем заданная "верхняя граница".
Поэтому в качестве программиста C я использую модифицированную версию функции arc4random_uniform()
для генерации равномерно распределенных псевдослучайных чисел.
Проблема в том, что я не понимаю, как функция работает математически.
Это пояснительный комментарий функции, за которым следует ссылка на полный исходный код:
/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by generating new random numbers until the one
* returned is outside the range [0, 2**32 % upper_bound). This
* guarantees the selected random number will be inside
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
* after reduction modulo upper_bound.
*/
В приведенном выше комментарии мы можем определить:
-
[2^32 % upper_bound, 2^32)
- интервал A -
[0, upper_bound)
- интервал B
Для работы функция полагается на то, что интервал A отображает на интервал B.
Мой вопрос: математически, как числа в интервале A равномерно отображают числа в интервале B? И есть ли доказательство этого?