Вопрос по random, c – Создает ли n * (rand () / RAND_MAX) перекошенное распределение случайных чисел?

9

Я хотел бы найти неискаженный способ получения случайных чисел в C (хотя в большинстве случаев я собираюсь использовать его для значений 0-20, и, скорее всего, только 0-8). Я видел эту формулу, но после выполнения некоторых тестов я не уверен, что она искажена или нет. Любая помощь?

Вот полная используемая функция:

int randNum() 
{ 
    return 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
}

Я посеял это используя:

unsigned int iseed = (unsigned int)time(NULL);
srand (iseed);

Предложенный ниже отказывается работать на меня, я пытался

int greek; 
for (j=0; j<50000; j++) 
{ 
greek =rand_lim(5); 
printf("%d, " greek); 
greek =(int) (NUM * (rand() / (RAND_MAX + 1.0))); 
int togo=number[greek]; 
number[greek]=togo+1; 
}

и он перестает работать и дает мне то же число 50000 раз, когда я комментирую printf.

Что такоеNUM?? Hot Licks
& APOS не должен; тRAND_MAX + 1.0 быть простоRAND_MAX? Ed Heal
Какие тесты вы проводили? user554546
@MarkRansom - я это знаю. Вопрос требует значений в диапазоне 0-20. Таким образом, формула просто потребует деления на RAND_MAX, так как она не упоминает, что диапазон не исключает 20. Ed Heal
@EdHeal, если вы хотите, чтобы интервал был[0.0,1.0) (т.е. не включая 1.0) вы должны разделить больше, чем RAND_MAX, хотя я думаю, что значение меньше, чем1.0 будет работать лучше. Mark Ransom

Ваш Ответ

1   ответ
16

Если вы возьмете числа от 0 до RAND_MAX и попытаетесь разделить их на 10 стопок, у вас действительно будет только три возможности:

RAND_MAX is a multiple of 10, and the piles come out even. RAND_MAX is not a multiple of 10, and the piles come out uneven. You split it into uneven groups to start with, but throw away all the "extras" that would make it uneven.

Вы редко контролируете RAND_MAX, и в любом случае это часто простое число. Это действительно оставляет 2 и 3 как возможности.

Третий вариант выглядит примерно так: [Правка: после некоторого размышления я пересмотрел это, чтобы получить числа в диапазоне 0 ... (предел-1), чтобы соответствовать тому, как работает большинство вещей в C и C ++. Это также упрощает код (чуть-чуть).

int rand_lim(int limit) {
/* return a random number in the range [0..limit)
 */

    int divisor = RAND_MAX/limit;
    int retval;

    do { 
        retval = rand() / divisor;
    } while (retval == limit);

    return retval;
}

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

#include <stdlib.h>
#include <stdio.h>

#define MAX 1009

int next_val() {
    // just return consecutive numbers
    static int v=0;

    return v++;
}

int lim(int limit) {
    int divisor = MAX/limit;
    int retval;

    do {
        retval = next_val() / divisor;
    } while (retval == limit);

    return retval;
}

#define LIMIT 10

int main() {

    // we'll allocate extra space at the end of the array:
    int buckets[LIMIT+2] = {0};
    int i;

    for (i=0; i<MAX; i++)
        ++buckets[lim(LIMIT)];

    // and print one beyond what *should* be generated
    for (i=0; i<LIMIT+1; i++)
        printf("%2d: %d\n", i, buckets[i]);
}

Итак, мы начинаем с чисел от 0 до 1009 (простое число 1009, поэтому оно не будет точным кратным любому диапазону, который мы выберем). Итак, мы начинаем с 1009 чисел и разбиваем их на 10 сегментов. Это должно дать 100 в каждом ведре, и 9 остатков (так сказать) «съедаются» посредствомdo/while петля. Как написано в данный момент, он выделяет и распечатывает дополнительное ведро. Когда я запускаю его, я получаю ровно 100 в каждом из сегментов 0..9 и 0 в сегменте 10. Если я закомментируюdo/while цикл, я вижу 100 в каждом из 0,9 и 9 в ведро 10.

Просто чтобы быть уверенным, я перезапустил тест с различными другими числами как для полученного диапазона (в основном используются простые числа), так и для количества сегментов. До сих пор я не смог добиться того, чтобы он давал искаженные результаты для любого диапазона (до тех пор, покаdo/while цикл включен, конечно).

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

Я должен также указать, что тамare генераторы, которые делают примерно наоборот - младшие биты более случайны, чем старшие биты. По крайней мере, по моему опыту, это довольно редко. То, с чем старшие биты являются более случайнымиconsiderably чаще.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Robert
Error: User Rate Limit Exceeded Robert
Error: User Rate Limit Exceeded Robert
Error: User Rate Limit Exceeded0Error: User Rate Limit ExceededRAND_MAXError: User Rate Limit ExceededRAND_MAX + 1Error: User Rate Limit ExceededRAND_MAX + 1Error: User Rate Limit Exceeded

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