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

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

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

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

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

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

Благодарность,

m


random math srand
person Michael Xu    schedule 04.05.2010    source источник
comment
Обратите внимание, что srand задает rand, а srandom задает random.   -  person outis    schedule 05.05.2010
comment
Мне было бы интересно узнать вариант использования, стоящий за этим - я думаю, что что-то упускаю, так как не понимаю, почему 100 000-я последовательность более случайна, чем первая.   -  person HorusKol    schedule 22.02.2011
comment
@HorusKol Прошло некоторое время, но, оказавшись здесь через Google, когда меня интересует что-то связанное, я действительно хочу дать вам пример использования. Представьте себе игру, которая дает вам серию головоломок, каждая из которых генерируется из одного числа. Чтобы убедиться, что каждый человек получает разные головоломки, вы используете генератор случайных чисел и запоминаете начальное семя. Теперь вы можете захотеть, чтобы пользователь мог продолжить с того места, где он ушел (в это время известно семя, что упрощает задачу) или даже переиграть любую головоломку, пока он помнит ее номер.   -  person Jasper    schedule 28.07.2012
comment
(Да, мне пришлось немного растянуть его, чтобы получить полный вариант использования. Однако идея в том, что речь идет не о большей случайности, а о воссоздании чего-то случайного (таким образом фактически превращая псевдочасть случайности в преимущество).   -  person Jasper    schedule 28.07.2012

Ответы (4)


arrow_upward
2
arrow_downward

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

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

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

xn+1 = (a xn + c) по модулю m

с a = 1103515245, c = 12345 и m = 231. Начальное значение указывает начальное значение x1. Период этого генератора равен 231, и он использует 1 слово памяти на генератор.

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

Если мы начнем с x1...

  • х2 = (a * x1 + c) % м
  • x3 = (a * ((a * x1 + c) % m) + c) % m
  • x4 = (a * ((a * ((a * x1 + c) % m) + c) % m) + c) % m
  • x5 = (a * (a * ((a * ((a * x1 + c) % m) + c) % m) + c) % m ) + в) % м

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

(Есть статистическая фраза для серии, где xn зависит от xn-1 — кто-нибудь может напомнить мне, что это за слово?)

person Mark Rushakoff    schedule 04.05.2010
comment
RE: статистическая фраза. Цепь Маркова первого порядка? Хотя в данном случае это не совсем так, поскольку x_n не зависит от x_(n-2). - person outis; 05.05.2010
comment
Это не цепь Маркова. По сути, это просто рекуррентное соотношение для целых чисел по модулю 2^31. - person sigfpe; 05.05.2010
comment
Кстати, это рекуррентное соотношение довольно легко решить. Помните, что вы можете вывести все эти % m операции в одно приложение % m в конце. Полученное отношение является примером из учебника. Но превращение его в эффективный и полезный фрагмент кода требует немного больше работы, потому что его применение наивно требует целых чисел произвольной точности. Но я думаю, что может быть способ получить это частично под контролем. - person sigfpe; 05.05.2010

arrow_upward
1
arrow_downward

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

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

person outis    schedule 04.05.2010

arrow_upward
1
arrow_downward

Это разработано на основе ответа @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, используя всего несколько строк кода.

person sigfpe    schedule 04.05.2010

arrow_upward
0
arrow_downward

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

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

person NotMe    schedule 04.05.2010