Функция C random() и setstate не работает должным образом

Question

Я не уверен, почему эти два блока кода дают разные результаты:

unsigned int seed1 = 0;
char state1[256];
initstate(seed1, state1, 256);
printf("%10ld\n", random());
printf("%10ld\n", random());
// Gives:
// 1216130483
// 1950449197

против

unsigned int seed1 = 0;
char state1[256];
initstate(seed1, state1, 256);
printf("%10ld\n", random());
setstate(state1);
printf("%10ld\n", random());
// Gives:
// 1216130483
// 625602885

Я неправильно понимаю, что делает setstate()?

РЕДАКТИРОВАТЬ: Достаточно интересно, посмотрите, что это дает:

unsigned int seed1 = 0;
char state1[256];
initstate(seed1, state1, 256);
printf("%10ld\n", random());
setstate(state1);
setstate(state1);
printf("%10ld\n", random());
// Gives:
// 1216130483
// 1950449197

Answer 1

Обе реализации верны.

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

Initstate может делать то же самое, но также может сначала изменить содержимое буфера. Если PRNG является чем-то вроде ARC4 или Spritz, буфер должен быть перестановкой, а не просто произвольными битами. Если PRNG является нелинейным аддитивным генератором обратной связи, то необходимо установить хотя бы один из младших битов где-то в состоянии, иначе он не будет работать правильно. А некоторые библиотеки хэшируют буфер состояния, поэтому будет нелегко определить, какой тип PRNG используется, только по информации seed+output. Они не обязаны; lib может сделать то же самое для initstate и setstate, если генератор, который он использует, - это LFSG или что-то, что не требует какого-либо определенного формата или требует согласованности для буфера. Но если вы не делаете initstate и ваша ОС использует что-то, что имеет такие потребности, ваша повторяемая последовательность может оказаться не такой непредсказуемой, как вам бы хотелось.

Answer 2

Я думаю, звонок initstate() также не переключается в это состояние, но вызов setstate() делает, поэтому последний random() call возвращает номер, сгенерированный из нового состояния.

Answer 3

Реализация BSD setstate загружает вспомогательную информацию о состоянии для проверки ошибок перед сохранением в старом буфере. Дополнительно initstate а также setstate являются единственными функциями, которые обновляют эту информацию. Это означает, что при использовании того же буфера он загружает устаревшее состояние, сохраняет новые данные и обновляет внутреннее состояние первым. призвание setstate таким образом, несколько раз будут чередоваться старое сохраненное состояние и текущее внутреннее состояние, вызывая результаты, наблюдаемые при вызове дважды.

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

Обратите внимание, что из-за порядка, в котором все делается, можно вызывать setstate() с тем же состоянием, что и текущее состояние.

Answer 4

initstate() сообщает random, какой буфер использовать для хранения информации для следующего случайного числа. Вы получаете разные ответы в звонках на random() потому что информация в вашем буфере state1[256] изменился Посмотрите на вывод следующего кода:

#define LEN (32)
void print_hex( char *b)
{
   int i;
   for( i=0; i < LEN; i++) printf("%02x ",((unsigned char *)b)[i]);     
   printf("\n");
}

main()
{
   char state1[256], state2[256], tmp[256];
   initstate( 42, state2, LEN);
   initstate( 62, state1, LEN) ;
   printf("buffer before random():\n");
   print_hex( state1 ) ;
   printf("%10ld\n", random());
   printf("buffer after random():\n");
   print_hex( state1 ) ;

   setstate( state2 ); // Now we are free to copy data from state1
   printf("buffer after setstate():\n");
   print_hex( state1 ) ;
   memcpy( tmp, state1, 256);
   printf("copied to tmp\n");

   setstate( state1 ); // Go on with original sequence
   printf("next random():\n") ;
   printf("%10ld\n", random());
   printf("next random():\n") ;
   printf("%10ld\n", random());

   setstate( state2 ) ; // Again, this allows us to play with data in state1
   memcpy( state1, tmp, 256);
   setstate( state1 ) ;
   printf("back copy:\n");
   printf("random() after copy:\n") ;
   printf("%10ld\n", random());
   printf("next random():\n") ;
   printf("%10ld\n", random());
}

Это дает вывод:

buffer before random():
01 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 35 2b 97 b5 76 8c ff a8 56 14 14 7b ba 19 d9 f7
1801070350
buffer after random():
01 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 1c 4e b4 d6 76 8c ff a8 56 14 14 7b ba 19 d9 f7
buffer after setstate():
06 00 00 00 e7 22 1d 21 f1 62 9c 90 89 72 b5 89 1c 4e b4 d6 76 8c ff a8 56 14 14 7b ba 19 d9 f7
copied to tmp
next random():
 483260339
next random():
  40158063
back copy:
random() after copy:
 483260339
next random():
 40158063

Вы можете увидеть это после первого звонка random() содержимое буфера state1 изменения. random() использует эту область для хранения своего состояния. Это состояние копируется в буфер tmp, Позже мы копируем его обратно в state1и получить ту же последовательность случайных чисел. Обратите внимание, что прежде чем копировать в или из буфера, который должен использоваться для случайных чисел, вы должны сообщить random() прекратить использование этого буфера с помощью setstate() или же initstate(), Причина в том, что когда setstate() вызывается, старый буфер изменяется, чтобы он мог быть снова загружен setstate(),

Таким образом, чтобы получить тот же ответ, что и в исходном вопросе, вы должны использовать:

unsigned int seed1 = 42;
char state1[256], tmp[256];
initstate(seed1, state1, 256);
printf("%10ld\n", random());
initstate( 0, tmp, 256); // <- notice this
setstate( state1 ) ;
printf("%10ld\n", random());