可逆伪随机序列发生器 [英] Reversible pseudo-random sequence generator

问题描述

我想要某种方法来创建一个相当长的随机数序列，我可以前后翻转.就像一台带有下一个"和上一个"按钮的机器，它会给你随机数.

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

我们可以重新排序:

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

由于 a 和 m 被选为 lcg 中的互质数，我们可以使用扩展的 euclid 算法找到逆.

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和a，算法可以有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屋！