Реализация простенького линейного конгруэнтного генератора на СИ

Question

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

int lcg(int seed){
    int m = 0xfffffff;
    int c = 1;
    int a = 22695477;
    int result = (a * seed + c) % m;
    return result;
}


int main() {
    time_t t;
    int start = time(&t);
    int a[10] = { 1,-23,101,0,111,45,390,-909,1000000,-60 };
    int r = lcg(start) % 10;
    while (1) {
        r = lcg(time(&t)) % 10;
        printf("[%d]", a[r]);
        getchar();
    }
    return 0;
}

Вторая версия после правки:

int lcg(int seed){
    int m = 0xfffffff;
    int c = 1;
    int a = 22695477;
    int result = (a * seed + c) % m;
    return result;
}


int main() {
    time_t t;
    int start = time(&t);
    int a[10] = { 1,-23,101,0,111,45,390,-909,1000000,-60 };
    int r = lcg(start) % 10;
    while (1) {
        r = lcg(time(&t)) % 10;
        if (r < 10) {
            printf("[%d]", a[r]);
        }
        else {
            continue;
        }
        getchar();
    }
    return 0;
}

Answer 1

В операции

int result = (a * seed + c) % m;

вы легко можете получить переполнение, которое хотя формально является для знаковых типов UB (впрочем, не уверен, что там в самом последнем стандарте), но на практике дает отрицательное значение.

Так что не думаю, что вас спасла проверка if (r < 10); проблема в другой стороне диапазона... Подумайте о том, как изменить ваш код.

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

Update
Все же решил за 5 минут набросать простейший тест, сколько разных чисел генерирует ваш генератор... Диапазон небольшой, так что тупо через вектор. Оказалось, что все даже хуже, чем я предполагал.

Вот ваш слегка подправленный (чтоб выдавал последовательность чисел) код генератора + эксперимент:

int lcg(int seed = -1)
{
    static int result = 0;
    if (seed >= 0) result = seed;
    int m = 0xfffffff;
    int c = 1;
    int a = 22695477;
    result = (a * result + c) % m;
    if (result < 0) result = -result;
    return result;
}

int main(int argc, char * argv[])
{
    for(int i = 0; i < 20; i+=2)
    {
        lcg(time(0)+i);
   
        int M = 0, C = 0;
        vector<bool> v(0xfffffff);
        for(;;)
        {
            int x = lcg();
            if (v[x]) break;
            ++C;
            if (M < x) M = x;
            v[x] = true;
        }
        cout << C << "  " << M << endl;
    }
}

Я даже не стал мучиться с каким-нибудь хи-квадрат тестом, для генератора, который не в состоянии выдать более 20000 разных чисел, ставить вопрос о статистике не имеет смысла. Крайне рекомендую обратиться к тому 2 "Искусства программирования" Кнута; в крайнем случае возьмите у него готовую реализацию.

До того, как в С++11 вошел нормальный <random>, я пользовался вот таким генератором имени Кнута :):

int rng(int seed = -1)
{
    static int X = 1;
    if (seed >= 0) X = seed;
    const int MM = 2147483647;
    const int AA =      48271;
    const int QQ =      44488;
    const int RR =       3399;
    X = AA*(X%QQ)-RR*(X/QQ);
    if (X < 0) X += MM;
    return X-1;
}

Этот в экспериментах стабильно выдает все 2147483646 разных чисел — от 0 до 2147483645... 64-разрядную версию предлагать не стану :)

БЛОГ НА HUSL

Реализация простенького линейного конгруэнтного генератора на СИ

Ответы (1 шт):