Вопрос по c, algorithm, statistics, integer, uniform – Генерация равномерного распределения INTEGERS в C

10

Я написал функцию C, которая, по моему мнению, выбираетintegers изuniform distribution с диапазоном [rangeLow, rangeHigh], включительно. Это не домашнее задание - я просто использую его в некоторых встроенных системах, которые я делаю для развлечения.

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

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

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

Для приличной случайности вам, возможно, придется пойти на что-то специфичное для платформы или, по крайней мере, использовать что-то вне стандарта C, например Функции POSIX или BSD-spec dreamlax

Ваш Ответ

4   ответа
1

Версия, которая исправляет ошибки распространения (отмечено Лиором), включает в себя старшие биты, возвращаемые rand () и использует только целочисленную математику (если это желательно):

int uniform_distribution(int rangeLow, int rangeHigh)
{
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int copies=RAND_MAX/range; // we can fit n-copies of [0...range-1] into RAND_MAX
    // Use rejection sampling to avoid distribution errors
    int limit=range*copies;    
    int myRand=-1;
    while( myRand<0 || myRand>=limit){
        myRand=rand();   
    }
    return myRand/copies+rangeLow;    // note that this involves the high-bits
}

// примечание: убедитесь, что rand () уже инициализирован с помощью srand ()

Это должно работать хорошо при условии, чтоrange намного меньше чемRAND_MAX, иначе Вы вернетесь к проблеме,rand() не является хорошим генератором случайных чисел с точки зрения его младших битов.

Вы имели в виду myRand & lt; 0 || myRand & gt; = предел, нет? А почему бы не использовать do while?
@Marc Я систематически использую полуоткрытые интервалы для подобных вещей; c.f.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html  и избегайте do-while как части моего "стиля".
Хорошо, Дейв, но myRand никогда не будет и тем и другим. 0 и & gt; = предел.
12

Предположим, что rand () генерирует равномерно распределенное значение I в диапазоне [0..RAND_MAX], и вы хотите сгенерировать равномерно распределенное значение O в диапазоне [L, H].

Предположим, что I in является диапазоном [0..32767], а O находится в диапазоне [0..2].

Согласно предложенному вами методу O = I% 3. Обратите внимание, что в данном диапазоне есть 10923 числа, для которых I% 3 = 0, 10923 числа, для которых I% 3 = 1, но только 10922 числа, для которых I% 3 = 2. Следовательно, ваш метод не будет отображать значение из I в O равномерно.

В качестве другого примера, предположим, что O находится в диапазоне [0..32766].

Согласно предложенному вами методу O = I% 32767. Теперь вы получите O = 0 как для I = 0, так и для I = 32767. Следовательно, 0 в два раза чаще, чем любое другое значение - ваш метод снова неоднороден.


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

  1. Calculate the number of bits that are needed to store a random value in the range [L,H]:

    unsigned int nRange = (unsigned int)H - (unsigned int)L + 1;
    unsigned int nRangeBits= (unsigned int)ceil(log((double(nRange) / log(2.));

  2. Generate nRangeBits random bits

    this can be easily implemented by shifting-right the result of rand()

  3. Ensure that the generated number is not greater than H-L. If it is - repeat step 2.

  4. Now you can map the generated number into O just by adding a L.

Я сослался на этот хороший ответhere, Небольшое улучшение кандидатаceil(log((double(nRange) / log(2.)) - & GT;ceil(log2((double)nRange)) или какое-либо другое целочисленное вычисление.
3

Я думаю, что известно, что rand () не очень хорош. Это зависит только от того, насколько хорошо «случайный» данные вам нужны.

Я полагаю, вы могли бы написать тест, а затем вычислить значение хи-квадрат, чтобы увидеть, насколько хорош ваш генератор униформ:

http://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test

В зависимости от вашего использования (не используйте это для своего покера в Интернете), вы можете рассмотреть LFSR

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

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

6

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

int uniform_distribution(int rangeLow, int rangeHigh) {
    double myRand = rand()/(1.0 + RAND_MAX); 
    int range = rangeHigh - rangeLow + 1;
    int myRand_scaled = (myRand * range) + rangeLow;
    return myRand_scaled;
}

С помощьюrand() этот способ приведет к смещению, как отметил Лиор. Но техника хороша, если вы можете найти генератор единой чисел для расчетаmyRand, Один из возможных кандидатов будетdrand48(), Это значительно сократит смещение до того, что будет очень трудно обнаружить.

Однако если вам нужно что-то криптографически безопасное, вы должны использовать алгоритм, изложенный в ответе Лиора, предполагая, чтоrand() сам по себе криптографически защищен (по умолчанию, вероятно, нет, поэтому вам нужно будет его найти). Ниже приведена упрощенная реализация того, что описал Лиор. Вместо того, чтобы считать биты, мы предполагаем, что диапазон находится в пределахRAND_MAXи вычислить подходящее кратное число. В худшем случае алгоритм заканчивает тем, что в среднем дважды вызывает генератор случайных чисел на запрос числа в диапазоне.

int uniform_distribution_secure(int rangeLow, int rangeHigh) {
    int range = rangeHigh - rangeLow + 1;
    int secureMax = RAND_MAX - RAND_MAX % range;
    int x;
    do x = secure_rand(); while (x >= secureMax);
    return rangeLow + x % range;
}
Это должно быть «return rangeLow + x% range;».
Я использовал это в своем коде. :) solvingPuzzles

Похожие вопросы