可逆伪随机序列发生器 [英] Reversible pseudo-random sequence generator
问题描述
我想一些方法来创建随机数的相当长序列，我可以通过向后和向前翻转。喜欢用下一个和previous按钮，一台机器，会给你随机数。
I would like some sort of method to create a fairly long sequence of random numbers that I can flip through backwards and forwards. Like a machine with "next" and "previous" buttons, that will give you random numbers.
像10位分辨率（即，在一个范围内的正整数，从0到1023）的东西就足够了，和> 100k的数字序列。它是一个简单的游戏类型的应用程序，我不需要加密强度的随机性或什么，但我希望它感到相当随机的。我有一个内存的有限虽然可用，所以我不能只是生成随机数据块，并通过它去。我需要互动时间来获得号码 - 我可以很容易地花几个毫秒想着下一个号码，但不舒服远不止于此。它最终将在一些微控制器的运行，可能只是一个Arduino。
Something like 10-bit resolution (i.e. positive integers in a range from 0 to 1023) is enough, and a sequence of >100k numbers. It's for a simple game-type app, I don't need encryption-strength randomness or anything, but I want it to feel fairly random. I have a limited amount of memory available though, so I can't just generate a chunk of random data and go through it. I need to get the numbers in "interactive time" - I can easily spend a few ms thinking about the next number, but not comfortably much more than that. Eventually it will run on some sort of microcontroller, probably just an Arduino.
我可以用一个简单的线性同余发生器（LCG）做到这一点。展望前锋很简单，往回走我不得不每隔一段时间缓存最新的数字和存储一些点，这样我就可以从那里重新序列。
I could do it with a simple linear congruential generator (LCG). Going forwards is simple, to go backwards I'd have to cache the most recent numbers and store some points at intervals so I can recreate the sequence from there.
但也许有一些伪随机数发生器，可以让你去这两个前锋和前锋？它应该是可能的挂钩两个线性反馈移位寄存器（的LFSR）在不同的方向滚动，无？
But maybe there IS some pseudo-random generator that allows you to go both forwards and forwards? It should be possible to hook up two linear feedback shift registers (LFSRs) to roll in different directions, no?
也许我可以只是错乱使用某种类型的哈希函数的索引号上车吗？我将首先尝试。
Or maybe I can just get by with garbling the index number using a hash function of some sort? I'm going to try that first.
任何其他的想法？
推荐答案
我问一个非常类似的问题在tigsource论坛。
至少在游戏中，散列函数可能可以做你想做的。你可以不喜欢这样
At least in games, a hash function could probably do what you want. You could do it like this
class ReversibleRNG {
int x;
public:
ReversibleRNG(int seed) : x(seed) {}
int next(){return yourFavoriteHash(++x);}
int prev(){return yourFavoriteHash(--x);}
};
双向线性同余发生器（LCG）
多重人指出，一个LCG确实是可逆的。在一个LCG，下一状态计算是这样的：
Reversible linear congruential generator (lcg)
As multiple people have pointed out, an lcg is indeed reversible. In an lcg, the next state is computed like this:
x = (a * prevx + c) mod m
我们可以重新排列如下：
We can reorder this:
x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)
由于和m选择为在一个LCG互质，我们可以通过使用扩展欧几里得算法找到逆
Since a and m are chosen to be relatively prime in an lcg, we can find the inverse by using the extended euclid's algorithm.
ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)
这意味着
prevx = ainverse * (x - c) mod m
如果您选择M和细心，该算法可以有一段2 ^ 64
If you choose m and a carefully, the algorithm can have a period of 2^64
我做了一个仅标头的情况下，任何人实施该算法的是有兴趣的。
I did a header-only implementation of this algorithm in case anyone's interested.
这篇关于可逆伪随机序列发生器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
