рандомный генератор не повторяющихся чисел

leo

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

 

Вроде есть какая то теорема, что чисто математическими методами невозможно сделать генератор с бесконечным периодом.

 

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

qqwe

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

 

Y_Mur

не понял? где вы этот момент увидели?

дык пишу ж. если шаг будет некратный, для простоты длина последовательности - простое число, запетлевание обозначится прохождением стартового индекса. в этот момент можно взять другой некратный шаг (если длина простая, то просто любое другое ненулевое число. вплоть до элементарного ((rdtsc() >> N) & M) + 1 будет достаточно случайно)

мнээ, случай простой длины (CHAIN_MAX_LEN) последовательности

Код (Text):

1. unsigned get_nxt_rnd(){
2.   static unsigned step;
3.   static unsigned res = 0;
4.   static unsigned pos = 0;
5.   unsigned i;
6.  
7.   if(pos == 0){
8.     step = ((rdtsc() >> N) & M) + 1;
9.   }
10.  
11.   for(i = step; i > 0; i--, pos++){
12.     if(pos > CHAIN_MAX_LEN){
13.       pos = 0;
14.       res = 0;
15.     }
16.     res = get_next_in_chain(pos, res);
17.   }
18.  
19.   return res;
20. }

гдето так. все просто.

 

qqwe
rdtsc это уже не математический псевдослучайный генератор, а "истинно случайный", основанный на реальных событиях, он в отличие от математического не запетлёвывается но там проблемы с предсказумостью характера распределения случайной величины.
Для математического генератора псевдослучайных чисел выборка допустим чётных значений потом нечётных ничего не даст, поскольку при каждом проходе придётся посчитать все числа, отбрасывая "неподходящие", но в сумме количество чисел в этих двух и более "проходов по множеству" будет таким же как при одном проходе "подряд". Другое дело что действительно можно хранить стартовое число и по нему определять завершение петли, но в общем случае петля может и не захватывать стартовое значение, а начинаться позже и бегать по кругу, никогда не вернувшись к стартовому. Насколько я понял ТС как раз хотел диагностировать такой случай.

 

Y_Mur

это что, мат задача? можете инициализовать текущей секундой если хотите. как в учебниках. или еще чем.

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

A(длина посл) * N(количество проходов) / N(шаг) = А(количество прочитанных чисел)

для любых A и N. даже не кратных. точнее, для не кратных это будет единственный случай деления нацело.

 

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

 

LFSR — маскимальный период 2^n − 1 при использовании в качестве функции обратной связи примитивного полинома.
Реализация очень проста: http://wasm.ru/forum/viewtopic.php?pid=174110#p174110.