Почему мой код C генерирует только каждое третье случайное число?

Question

Я пытаюсь смоделировать распространение червя по сети, состоящей из 100 000 компьютеров. Само моделирование очень простое, и мне не нужна помощь, за исключением того, что по какой-то причине я получаю только каждое третье случайное число.

Только компьютеры с индексом по модулю 1000 меньше 10 могут быть заражены, поэтому, когда заражены 1000 компьютеров, программа должна быть завершена. По какой-то причине моя программа получает только 329. Когда я понижаю номер цели и проверяю содержимое массива, только каждый третий компьютер был изменен, и это закономерность. Например, в конце массива изменяются только компьютеры 98001, 98004, 98007, 99002, 99005, 99008, даже если компьютеры между ними (98002, 98003 и т. Д.) Также должны быть изменены. Шаблон содержит весь путь до начала массива. Когда я пытаюсь изменить все 1000, программа заходит в бесконечный цикл и застревает на 329.

Редактировать: Я только что обнаружил, что если я уменьшу NETSIZE до 10000, а цель в цикле while до 100, это ничего не пропустит. Означает ли это, что проблема связана с ошибкой округления? Кто-то, кто знает о Си больше, чем я, должен знать ответ.

Спасибо.

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

#define NETSIZE 100000

double rand01();
void initNetwork();

unsigned char network[NETSIZE];
int scanrate = 3;
int infectedCount;
int scans;
int ind;
int time;



int main(void) {
    initNetwork();
    time = 0;
    infectedCount = 1;
    while (infectedCount < 1000) { //changing 1000 to 329 stops the infinite loop
        scans = infectedCount * scanrate;
        for (int j = 0; j < scans; j++) {
            ind = (int) (rand01() * NETSIZE);
            if (network[ind] == 0) {
                network[ind] = 1;
                infectedCount++;
            }
        }
        time++;
    }
    for (int k = 0; k < NETSIZE; k++) {
        if (network[k] == 1) printf("%d at %d\n", network[k], k);
    }
}
double rand01() {
    double temp;
    temp = (rand() + 0.1) / (RAND_MAX + 1.0);
    return temp;
}

void initNetwork() {
    for (int i = 0; i < NETSIZE; i++) {
        if (i % 1000 < 10) {
            network[i] = 0;
        } else  {
            network[i] = 2;
        }
    }
    network[1000] = 1;
}

В приведенном выше коде я ожидаю, что код будет работать, пока 1000 уязвимых индексов не будут изменены с 0 на 1.

Answer 1

^{Преобразование комментариев в ответ.}

Что такое RAND_MAX в вашей системе?Если это 15-битное или 16-битное значение, вы, вероятно, не получите достаточно хорошее квантование при преобразовании в удвоение.Если это 31-битное или большее число, это (вероятно) не будет проблемой.Вам необходимо выяснить, какие значения генерируются только функцией rand01() с различными начальными значениями, плюс умножение и приведение к целому числу - просто выведите результаты и sort -n | uniq -c, чтобы увидеть, насколько однородны результаты.

В моей системе RAND_MAX всего 32767. Как вы думаете, возможно, поэтому мои результаты могут быть недостаточно детальными?Теперь, когда вы заставили меня задуматься, будет только 32 767 возможных значений, а мой сетевой массив - 100 000 возможных значений.Это соответствует примерно 1/3 результатов, которые я получаю.

Да, я думаю, что это, вероятно, проблема.Вам нужно 100 000 различных значений, но ваш генератор случайных чисел может генерировать только около 33 000 различных значений, что очень близко к вашей метрике 1: 3.Это также сразу объясняет, почему вы получили хорошие результаты, когда вы уменьшили множитель со 100 000 до 10 000.

Вы можете попробовать:

double rand01(void)
{
    assert(RAND_MAX == 32767);
    return ((rand() << 15) + rand()) / ((RAND_MAX + 1.0) * (RAND_MAX + 1.0));
}

Или вы можете использовать альтернативный генератор случайных чисел - например,POSIX определяет как семейство функций drand48(), так и random() с соответствующими функциями настройки посевного материала, где это необходимо.

Answer 2

Да, проблема, с которой я сталкиваюсь, состоит в том, что значение RAND_MAX в моей системе составляет всего 32767, и я пытаюсь эффективно распределить его по 100 000 значений, в результате чего появляется только каждое третье число.

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

@ JonathanLefflerзаслуживает похвалы за это решение.