可调周期的PRNG [英] PRNG with adjustable period
问题描述
我需要构建一个具有可调周期的就地伪随机数生成器.此外，一个时期内不得有任何碰撞.也就是说，以下内容必须返回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是不可接受的.它必须至少是有点随机.
我已经研究了线性同余生成器，但这似乎是针对我的特定约束的错误路径.
(除非是相对较快的(几秒钟)，否则不能选择强行使用暴力.)
我认为斐波那契线性反馈移位寄存器(LFSR)是一个不错的选择.
您可以从维基百科中获取相关信息和算法.
只是摘录:
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 N -1形式.
您可以克服这一点，注意在任何需要的时间段P中，选择为您提供下一个" 2 N -1值的N可能会留下2 (N-1)-从循环中抑制1个数字(因为如果您需要抑制更大的数字，只需使用N-1生成).
因此，要抑制k个值(k =(((2 N -1)-P)⋳{1 ...，2 (N-1)- 1})，您可以添加一些逻辑，例如
I need to build an in-place pseudo-random number generator with an adjustable period. In addition, there must be no collisions within one period. That is, the following must return 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;
}
(Example is pseudocode; an answer in any commonly readable language (C++, Python, Haskell, etc.) is acceptable.)
The PRNG must not depend on mutable static state when generating the numbers. That is, I can't have a large table of already-returned numbers or something like that. It should only rely on the given input for generating the next term.
The algorithm does not have to be cryptographically strong (of course), or "strongly" random. However, x % period is not acceptable; it has to be at least somewhat random.
I have looked into linear congruential generators, but that seems to be the wrong path to take for my specific constraints.
(Brute-forcing is not an option, unless it's relatively quick (a few seconds).)
I think a good candidate is a Fibonacci Linear Feedback Shift Register (LFSR).
You can get the relevant info and algorithms from Wikipedia.
Just an excerpt:
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.
The only problem is that the periods for the LFSR are always of the form 2N-1.
You could overcome this noting that for any wanted period P, choosing the N that gives you the "next" 2N-1 value leaves potentially 2(N-1)-1 numbers to supress from the cycle (because if you need to supress more than that, just generate with N-1).
So, to supress k values (k = ((2N-1) - P) ⋳ {1 ... ,2(N-1)-1}) you can add a little logic such as
If (Mod(cur,2(N-1)+1-k) == 0) Then
cur=Mod(cur+1,2N-1)
这篇关于可调周期的PRNG的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
