создать случайную последовательность, перейти к любой части последовательности

Question

В Linux.Существует функция srand (), в которой вы предоставляете начальное число, и она гарантирует ту же последовательность псевдослучайных чисел при последующих вызовах функции random () впоследствии.

Допустим, я хочу сохранить эту псевдослучайную последовательность, запомнив это начальное значение.

Кроме того, скажем, я хочу, чтобы 100-тысячное число в этой псевдослучайной последовательности было позже.

Один из способов - предоставить начальное число с помощью srand (), а затем вызвать random ()100 тысяч раз и запомнив это число.

Есть ли лучший способ пропустить все 99,999 других чисел в псевдослучайном списке и напрямую получить 100-тысячное число в списке.

спасибо,

м

Answer 1

Я не уверен, что существует определенный стандарт для реализации rand на любой платформе; однако, выбирая это из Научной библиотеки GNU :

- Генератор: gsl_rng_rand

Это генератор рандов BSD. Его последовательность

x _{n + 1} = (a x _n + c) мод m

с = 1103515245, с = 12345 и m = 2 ³¹ . Семя указывает начальное значение, x ₁ . Период этого генератора составляет 2 ³¹ , и он использует 1 слово памяти на генератор.

Итак, чтобы «знать» x _n , требуется, чтобы вы знали x _n-1 . Если нет какой-то очевидной схемы, которую я пропускаю, вы не можете перейти к значению без вычисления всех значений до него. (Но это не обязательно так для каждой rand реализации.)

Если мы начнем с х ₁ ...

• x ₂ = (a * x ₁ + c)% m
• x ₃ = (a * ((a * x ₁ + c)% m) + c)% m
• x ₄ = (a * ((a * ((a * x ₁ + c)% m) + c)% m) + c)% m
• x ₅ = (a * (a * ((a * ((a * x ₁ + c)% m) + c)% m) + c)% м) + в)% м

Очень быстро выходит из-под контроля. Эта функция легко сводима? Я не думаю, что это так.

_{(есть статистическая фраза для серии, где x n зависит от x n-1 - кто-нибудь может напомнить мне, что это за слово?)}

Answer 2

Это получено из ответа @ Mark с использованием функции BSD rand().

rand1() вычисляет n-е случайное число, начиная с seed, путем перехода n раз.

rand2() вычисляет то же самое с помощью ярлыка. Это может сделать до 2 ^ 24-1 шагов за один раз. Внутренне это требует всего 24 шага.

Если генератор случайных чисел BSD достаточно хорош для вас, этого будет достаточно:

#include <stdio.h>

const unsigned int m = (1<<31)-1;

unsigned int a[24] = {
    1103515245, 1117952617, 1845919505, 1339940641, 1601471041,
    187569281 , 1979738369, 387043841 , 1046979585, 1574914049,
    1073647617, 285024257 , 1710899201, 1542750209, 2011758593,
    1876033537, 1604583425, 1061683201, 2123366401, 2099249153,
    2051014657, 1954545665, 1761607681, 1375731713
};

unsigned int b[24] = {
    12345, 1406932606, 1449466924, 1293799192, 1695770928, 1680572000,
    422948032, 910563712, 519516928, 530212352, 98880512, 646551552,
    940781568, 472276992, 1749860352, 278495232, 556990464, 1113980928,
    80478208, 160956416, 321912832, 643825664, 1287651328, 427819008
};

unsigned int rand1(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<n; ++i)
    {
        seed = (1103515245U*seed+12345U) & m;
    }
    return seed;
}

unsigned int rand2(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<24; ++i)
    {
        if (n & (1<<i))
        {
            seed = (a[i]*seed+b[i]) & m;
        }
    }
    return seed;
}

int main()
{
    printf("%u\n", rand1 (10101, 100000));
    printf("%u\n", rand2 (10101, 100000));
}

Нетрудно адаптироваться к любому линейному конгруэнтному генератору. Я вычислил таблицы на языке с правильным целочисленным типом (Haskell), но я мог бы вычислить их другим способом в C, используя всего несколько строк кода.

Answer 3

Если они доступны в вашей системе, вы можете использовать rand_r вместо rand & srand или initstate и setstate с random. rand_r принимает unsigned * в качестве аргумента, где он хранит свое состояние. После многократного вызова rand_r сохраните значение этого целого числа без знака и в следующий раз используйте его в качестве начального значения.

Для random() используйте initstate вместо srandom. Сохраните содержимое буфера состояния для любого состояния, которое вы хотите восстановить. Чтобы восстановить состояние, заполните буфер кнопкой и вызовите setstate. Если буфер уже является буфером текущего состояния, вы можете пропустить вызов на setstate.

Answer 4

Если вам всегда нужен сотый тысячный предмет, просто сохраните его на потом.

Или вы можете сгенерировать последовательность и сохранить ее ... и запросить конкретный элемент по индексу позже.