代码之家 › 专栏 › 技术社区 › strager

周期可调的prng

random language-agnostic

strager · 技术社区 · 14 年前

我需要构建一个具有可调周期的就地伪随机数生成器。此外,在一段时间内不得发生碰撞。也就是说,以下内容必须返回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 不可接受;至少有点随机的。

我研究过线性同余生成器,但对于我的特定约束,这似乎是错误的。

(暴力不是一个选择,除非它相对快速(几秒钟)。)

1 回复 | 直到 14 年前

Dr. belisarius 14 年前

我认为一个好的候选人是 斐波纳契线性反馈移位寄存器(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 ⁿ -1个值可能留下2个 ^(n-1) -从循环中抑制1个数字(因为如果你需要抑制更多,只需用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,2^N-1)