Каков оптимальный алгоритм для создания несмещенного случайного целого в пределах диапазона?

Ответ 1

Проблема возникает, когда количество выходов генератора случайных чисел (RAND_MAX + 1) не равномерно делится на желаемый диапазон (max-min + 1). Так как будет последовательное отображение от случайного числа к выходу, некоторые выходы будут отображаться в более случайные числа, чем другие. Это независимо от того, как выполняется сопоставление - вы можете использовать модулю, деление, преобразование в плавающую точку, независимо от того, какой вуду вы можете придумать, основная проблема остается.

Масштабы проблемы очень малы, и нетребовательные приложения, как правило, могут уйти, игнорируя ее. Чем меньше диапазон и больший RAND_MAX, тем менее выраженный эффект будет.

Я взял вашу примерную программу и немного изменил ее. Сначала я создал специальную версию rand, которая имеет только диапазон 0-255, чтобы лучше продемонстрировать эффект. Я сделал несколько настроек для rangeRandomAlg2. Наконец, я изменил количество "шаров" до 1000000, чтобы улучшить согласованность. Вы можете увидеть результаты здесь: http://ideone.com/4P4HY

Обратите внимание, что версия с плавающей запятой создает две плотно сгруппированные вероятности, около 0.101 или 0.097, между ними нет ничего. Это предвзятость в действии.

Я думаю, что вызов этого "Java-алгоритма" немного вводит в заблуждение - я уверен, что он намного старше Java.

int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}

Ответ 2

Проблема в том, что вы выполняете операцию по модулю. Это не проблема, если RAND_MAX будет равномерно делиться вашим модулем, но обычно это не так. В качестве очень надуманного примера предположим, что RAND_MAX равно 11, а ваш модуль равен 3. Вы получите следующие возможные случайные числа и следующие полученные остатки:

0 1 2 3 4 5 6 7 8 9 10
0 1 2 0 1 2 0 1 2 0 1

Как вы можете видеть, 0 и 1 немного более вероятны, чем 2.

Одним из вариантов решения этой проблемы является выборка отбраковки: запрещая номера 9 и 10 выше, вы можете привести к тому, что результирующее распределение будет равномерным. Трудная часть - это выяснить, как сделать это эффективно. Очень хороший пример (тот, который занял у меня два дня, чтобы понять, почему он работает) можно найти в Java java.util.Random.nextInt(int).

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

int n = (int)(max - min + 1);
int remainder = RAND_MAX % n;
int x, output;
do {
  x = rand();
  output = x % n;
} while (x >= RAND_MAX - remainder);
return min + output;

РЕДАКТИРОВАТЬ: Исправлена ​​ошибка fencepost в приведенном выше коде, теперь она работает так, как должна. Я также создал небольшую пробную программу (С#; взяв единый PRNG для чисел от 0 до 15 и построил PRNG для чисел от 0 до 6 от него различными способами):

using System;

class Rand {
    static Random r = new Random();

    static int Rand16() {
        return r.Next(16);
    }

    static int Rand7Naive() {
        return Rand16() % 7;
    }

    static int Rand7Float() {
        return (int)(Rand16() / 16.0 * 7);
    }

    // corrected
    static int Rand7RejectionNaive() {
        int n = 7, remainder = 16 % n, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x >= 16 - remainder);
        return output;
    }

    // adapted to fit the constraints of this example
    static int Rand7RejectionJava() {
        int n = 7, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x - output + 6 > 15);
        return output;
    }

    static void Test(Func<int> rand, string name) {
        var buckets = new int[7];
        for (int i = 0; i < 10000000; i++) buckets[rand()]++;
        Console.WriteLine(name);
        for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]);
    }

    static void Main() {
        Test(Rand7Naive, "Rand7Naive");
        Test(Rand7Float, "Rand7Float");
        Test(Rand7RejectionNaive, "Rand7RejectionNaive");
    }
}

Результат выглядит следующим образом (вставка в Excel и добавление условной раскраски ячеек, чтобы различия были более очевидными):

Теперь, когда я исправил свою ошибку в отбракованной выборке, она работает так, как должна (до того, как она будет смещаться 0). Как вы можете видеть, метод float не идеален вообще, он просто распределяет смещенные числа по-разному.

Ответ 3

Легко понять, почему этот алгоритм создает смещенную выборку. Предположим, что ваша функция rand() возвращает однородные целые числа из набора {0, 1, 2, 3, 4}. Если я хочу использовать это для генерации случайного бита 0 или 1, я бы сказал rand() % 2. Множество {0, 2, 4} дает мне 0, а набор {1, 3} дает мне 1 - так ясно, что я пробовал 0 с 60% и 1 с 40% правдоподобием, неравномерным вообще!

Чтобы исправить это, вам нужно либо удостовериться, что ваш желаемый диапазон делит диапазон генератора случайных чисел, либо иначе отбрасывает результат, когда генератор случайных чисел возвращает число, большее, чем максимально возможное кратное целевому диапазону.

В приведенном выше примере целевой диапазон равен 2, самый большой множитель, который вписывается в диапазон случайной генерации, равен 4, поэтому мы отбрасываем любой образец, который не находится в наборе {0, 1, 2, 3}, и снова рулон.

Ответ 4

Самым простым решением является std::uniform_int_distribution<int>(min, max).