Обозначим ДСЧ0 датчик случайных чисел "мощности" 1000, который за первые 1000 последовательных вызовов выдаёт в случайном порядке числа от 0 до 999 (например: 666, 1, 113 ...), а потом "зацикливается", то есть начинает повторно выдавать ту же последовательность чисел (666, 1, 113...), и далее так и выдает их такими "циклами" по 1000 чисел.

Построим на основе ДСЧ0 следующий датчик случайных чисел ДСЧ:

1) возьмем массив размером 1000 ( M(0 to 999) ) и заполним его как-нибудь числами от 0 до 999, например, по возрастанию (0, 1, 2, 3 ... 999);

2) создадим переменную А ("адрес") с начальным значением 0;

3) при каждом вызове ДСЧ будем поступать следующим образом:

а) вызываем ДСЧ0: Х0 = ДСЧ0();

б) увеличиваем А на Х0 по модулю 1000: А = (А + Х0) mod 1000;

в) берем число по адресу А в качестве "выхода" ДСЧ: ДСЧ = М(А);

г) сохраняем Х0 в ячейке А (вместо "использованного" значения): М(А) = Х0.

Вопрос: будет ли "зацикливаться" ДСЧ, а если будет, то начиная с какого "шага" (вызова) и с каким периодом?

Barlone,

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

В описанной в посте конкретной реализации этой идеи конкретные порождаемые ею параметры 499500 и 1000 получились соразмеримы, и из-за этого "увеличение мощности" оказалось незначительным. Но ведь можно сделать размер буфера не 1000,а 997 (например)...

... Но ведь можно сделать размер буфера не 1000,а 997 (например)...

Или не экономить на вызовах ДСЧ0 и реализовать схему:

А=ДСЧ0()
ДСЧ=М(А)
М(А)=ДСЧ0()

-- которая концептуально даже проще (тем, что не нужно заморачиваться с "арифметикой" приращения адреса А)

kealon(Ruslan),

1) должна быть основана на "слабом" датчике случайных чисел (с коротким циклом);

2) должна иметь намного больший цикл, в пределе -- вообще его не иметь.

-- типа, не более, чем N*ЧислоПерестановок(N)?

Обозначим для простоты последовательность, повторения которой мы ждём, -- 1, 2, ... N. Предположим, что после неё -- не позже чем через N*ЧислоПерестановок(N) вызовов ГСЧ -- мы наконец снова увидели эту ( 1, 2, ... N ) последовательность. Но появится ли после неё (после значения N) то же самое следующее значение, которые появилось -- после N -- в первый раз?

Basil A. Sidorov,

понятно, что если однажды при некотором значении А0=ДСЧ0() -- "состояние" массива М будет в точности (во всех ячейках!) тем же самым, которое было ранее при некотором предыдущем появлении этого А0, то в этой точке ряд значений ДСЧ зациклится.

-- одномерное распределение, то есть распределение рассматриваемых по отдельности значений в ряду, возвращаемом ДСЧ()? Да, равномерное, точнее -- такое же, как и у ДСЧ0; а поскольку оно равномерное, то и от ДСЧ мы вправе требовать равномерности.

-- это мне напоминает коллизию, которая была в Как отбирать из потока 1/1000 лучших экземпляров? :

я говорю: в трубе течёт вода, нужно делать с этой водой то-то и то-то.

мне отвечают: сколько там той воды! вырой бассейн, собери в него всю воду и делай спокойно с водой в бассейне своё "то-то и то-то".

Aleksandr Sharahov,

задача -- повысить "мощность" ДСЧ (как и сказано в 22354962 )