Генерация псевдослучайного числа генерирует повторяющиеся значения

Question

Я использую свой класс Random для генерации чисел.

class Random {
    UInt128 seed;
    public Random(UInt128 seed) {
        this.seed = seed;
    }
    public int Next(int maxValue) {
        NextSeed();
        return (int)((seed * seed * 158 + 52185) % (UInt128)maxValue);
    }
    public void NextSeed() {
        seed = (seed * seed + 1856237) % UInt128.MaxValue;
    }
}

Затем через цикл for (int i = 0; i < 16; i++) я генерирую эти случайные значения, и они разные. Однако при повторном вызове этого цикла генерируется тот же ряд чисел, хотя зерно должно быть другое, я его не переопределяю и использую один объект.

Вот для примера вывод рядов этих самых значений:

7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1
7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1
7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1
7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1
... // и т.д.

P.S. мне нужно использовать именно свой класс. И да, я знаю, что код ужасный, да и это приведение к UInt128 выглядит не очень хорошо.

Код тестирования:

Random random = new(27652582738);  // сид задан для примера
for (int j = 0; j < 32; j++) {
    for (int i = 0; i < 16; i++) {
        Console.Write(random.Next(16).ToString() + " ");
    }
    Console.Write("\n");
}

Answer 1

В этом коде 2 проблемы:

Переполнение, которое никак не контроллируется
Ошибки в математике

Вот например тот же код, который не страдает от переполнения

class Random
{
    UInt128 seed;
    public Random(UInt128 seed)
    {
        this.seed = seed;
    }
    public int Next(int maxValue)
    {
        NextSeed();
        return (int)(((BigInteger)seed * seed * 158 + 52185) % (BigInteger)maxValue);
    }
    public void NextSeed()
    {
        seed = (UInt128)(((BigInteger)seed * seed + 1856237) % (BigInteger)UInt128.MaxValue);
    }
}

Получаем такой вывод

7 9 7 7 1 1 7 9 1 9 7 7 7 1 1 9
7 7 1 7 7 9 9 7 1 7 1 1 1 1 7 7
7 7 7 9 7 1 1 7 7 1 9 7 7 9 7 9
7 1 7 7 1 7 9 7 7 7 7 7 7 9 7 1
7 9 7 7 7 9 7 7 7 7 7 1 7 1 7 7
7 7 7 1 1 1 1 9 7 7 7 7 7 7 9 7
7 1 7 7 7 1 1 7 7 7 7 7 1 7 7 1
...

Уже что-то более похоже на случайность. И видим, что во-первых все числа нечётные, во-вторых в последовательности участвует всего 3 разных числа.

Почему нечётные:

Вот у вас формула seed * seed * 158 где 158 - чётное число, а это значит что результатам этого умножения будет всегда чётное число. Следовательно если к нему прибавить нечётное 52185, то на выход пойдёт нечётное число. Следовательно, в выводе не может быть чётных чисел.

Почему всего 3 числа:

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

Ну и так далее. Выбранная формула просто не даст вам ожидаемого результата, собственно она и не является ГСПЧ.

Требование наличия 128-битного сида весьма странное и несовсем понятно, зачем. Хочется повозиться с хорошим ГСПЧ, вот вам реализация System.Random на базе алгоритма Xoshiro256. Есть альтернатива - более старый алгоритм ГСПЧ "Вихрь Мерсенна", вот реализация. Как видите, ГСПЧ с хорошим расперелением это немного больше, чем 2 строчки с умножением и взятием остатка. Поизучайте основные практики, каким образом производится приведение числа к пределу, заданному пользователем, и это не взятие остатка.

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

Вот, попробовал избавиться от отбрасывания бит из-за взятия остатка и заменил 158 на простое число 157, а 52185 на ближайшее простое число 52189.

class Random
{
    UInt128 seed;
    public Random(UInt128 seed)
    {
        this.seed = seed;
    }
    public int Next(int maxValue)
    {
        NextSeed();
        return (int)(((BigInteger)seed * seed * 157 + 52189) % UInt128.MaxValue * maxValue / ((BigInteger)UInt128.MaxValue + 1));
    }
    public void NextSeed()
    {
        seed = (UInt128)(((BigInteger)seed * seed + 1856237) % (BigInteger)UInt128.MaxValue);
    }
}

Получил вывод

0 9 15 12 11 5 15 1 13 12 15 8 3 7 5 10
8 6 13 6 11 2 15 0 12 15 10 6 9 7 13 2
11 15 5 4 6 1 10 7 8 9 2 11 7 8 13 8
9 4 4 1 15 11 9 0 1 8 6 13 1 6 7 2
3 5 13 9 6 2 14 4 10 14 9 2 4 15 15 13
5 2 9 9 5 2 15 8 9 0 10 4 7 1 1 3
0 13 5 0 5 13 8 14 6 1 11 11 12 12 15 5
0 13 6 15 4 12 2 4 6 14 7 14 2 13 14 12
5 8 6 14 9 11 12 14 2 3 0 4 5 4 10 5
8 0 8 14 15 10 6 1 11 11 5 5 11 12 6 11
...

Согласитесь, что так гораздо лучше? Но этот код всё равно пока что не претендует на ГСПЧ.

БЛОГ НА HUSL

Генерация псевдослучайного числа генерирует повторяющиеся значения

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