PRNG可调周期

Question

我需要建立一个周期可调的就地伪随机数发生器。另外，一个时期内不得有冲突。也就是说，以下必须返回true：

// 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中，等）中的答案为是可接受的。）

的PRNG必须而不是在生成数字时依赖于可变静态。也就是说，我不能拥有一个已经返回的数字或类似的东西。它只应该依靠给定的输入来生成下一个词。该算法不一定是密码强（当然），或“强”随机。但是，x % period是不可接受的;它必须至少有随机有点。

我已经看过线性同余发生器，但这似乎是我的具体约束所采取的错误路径。

（暴力破解是不是一种选择，除非它是相对快速（几秒钟）。）

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，选择给出“下一个”-1值的N，可能会从循环中抑制数字（（）因为如果你需要抑制更多，只需用N-1生成）。

所以，剿的k值（K =（（2 ^Ñ -1） - P）{⋳1 ...，2 ^（N-1） -1}），则可以添加一点点逻辑如

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