PRNG с регулируемым периодом

Question

Мне нужно построить генератор псевдослучайных чисел на месте с регулируемым периодом. Кроме того, в течение одного периода не должно быть никаких столкновений. То есть, следующий должен возвращать верно:

// prng is "generated" at run-time 
// (though a by-hand solution would work) 

bool test(func prng, int period) { 
    int seed = 0; // Any number should work 
    int cur = seed; 

    for (int i = 0; i <= period; ++i) { 
     cur = prng(cur); 

     if (cur == seed) { 
      if (i == period) { 
       // We hit our period on target 
       return true; 
      } 

      // Period too low (we hit our seed already!) 
      return false; 
     } 
    } 

    // Period too high 
    return false; 
} 

(пример псевдокод, ответ в любом широко читаемом языке (C++, Python, Haskell и т.д.) является приемлемым.)

ПСЧ должен а не зависят от изменяемого статического состояния при генерации чисел. То есть, у меня не может быть большой таблицы уже возвращенных чисел или чего-то подобного. Он должен полагаться только на данный ввод для генерации следующего термина.

Алгоритм не должен быть криптографически сильным (конечно) или «сильно» случайным. Однако x % period неприемлем; он должен быть как минимум несколько случайный.

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

(Brute форсирования не вариант, если это не относительно быстро (несколько секунд).)

Answer 1

Я думаю, что хороший кандидат является Фибоначчи линейной обратной связью регистра сдвига (LFSR).

Вы можете получить необходимую информацию и алгоритмы от Wikipedia.

Только выдержка:

 
The initial value of the LFSR is called the seed, and because the operation 
of the register is deterministic, the stream of values produced by the 
register is completely determined by its current (or previous) state. 
Likewise, because the register has a finite number of possible states, it must 
eventually enter a repeating cycle. However, an LFSR with a well-chosen 
feedback function can produce a sequence of bits which appears random and 
which has a very long cycle. 

Единственная проблема заключается в том, что периоды для LFSR всегда в форме 2 ^Н -1.
Вы можете преодолеть это, отметив, что за любой требуемый период P, выбрав N, который дает вам «следующее» 2 ^N -1 значение оставляет потенциально 2 ^(N-1) -1 номера для подавления от цикла (потому что, если вам нужно больше беспокоиться, просто сгенерируйте с помощью N-1).

Таким образом, чтобы подавить к значений (к = ((2 ^N -1) - P) ⋳ {1, ..., 2 ^(N-1) -1}), вы можете добавить немного логики таких как

 
    If (Mod(cur,2(N-1)+1-k) == 0) Then 
     cur=Mod(cur+1,2N-1)