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）是一个很好的候选者。

\n\n

您可以从维基百科获取相关信息和算法。

\n\n

只是摘录：

\n\n

LFSR 的初始值称为种子，并且由于寄存器的操作是确定性的，因此寄存器产生的值流完全由其当前（或先前）状态决定。\n同样，因为寄存器具有有限数量的可能状态，\n它最终必须进入重复循环。然而，具有精心选择的反馈函数的 LFSR 可以产生看似随机且具有很长周期的位序列。\n

\n\n

唯一的问题是 LFSR 的周期始终为 2 ^N -1 形式。^{\n您可以克服这个问题，注意对于任何想要的周期 P，选择为您提供“下一个”2 N}
-1 值的 N可能会留下 2 ^(N-1) -1 个数字来抑制循环（因为如果您需要抑制更多，只需用 N-1 生成）。

\n\n

因此，要抑制 k 值 (k = ((2 ^N -1) - P) \xe2\x8b\xb3 {1 ... ,2 ^(N-1) -1}) 您可以添加一些逻辑，例如\ n

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

\n