Быстро и безопасно определить случайное число в пределах диапазона

Question

Как бы я быстро и безопасно * определил бы случайное число в диапазоне от 0 (включительно) до r (исключая)?

Другими словами, оптимизированная версия выборки отклонения:

u32 myrand(u32 x)
{
    u32 ret = rand();

    while(ret >= x)
        ret = rand();

    return(ret);
}

* Под безопасностью я подразумеваю равномерное распределение.

Answer 1

Выборка отклонения - это путь, если вы хотите иметь равномерное распределение по результату. Общеизвестно, что делать что-то умнее сложно. Например, использование оператора по модулю приводит к неравномерному распределению значений результата для любого числа, которое не является степенью 2.

Алгоритм в вашем посте, однако, может быть улучшен путем отбрасывания ненужных наиболее значимых битов. (См. Ниже.)

Вот как стандартный Java API реализует Random.nextInt(int n):

public int nextInt(int n) {

    [...]

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

    int bits, val;
    do {
        bits = next(31);
        val = bits % n;
    } while (bits - val + (n-1) < 0);

    return val;
}

А в комменсе вы можете прочитать:

Алгоритм немного хитрый. Он отклоняет значения, которые могут привести к неравномерному распределению (из-за того, что 2 ³¹ не делится на n ). Вероятность отклонения значения зависит от n. Худший случай - n = 2 ³⁰ + 1, для которого вероятность отклонения равна 1/2, а ожидаемое число итераций до завершения цикла равно 2.

Answer 2

u32 myrand(u32 x)
{
    return rand() % (x+1);
}

Поскольку вопрос был изменен, чтобы включить равномерное распределение, для этого потребуется нечто похожее на это:

u32 myrand(u32 x)
{
   assert(x <= RAND_MAX && x > 0);
   int numOfRanges = (RAND_MAX % x);
   int maxAcceptedRand = numOfRanges * x;
   int randNumber;
   do
   {
      randNumber = rand();
   }
   while(randNumber <= maxAcceptedRand);
   return number / numOfRanges;
}