reverse - 可逆伪随机序列发生器

Question

我想要某种方法来创建一个公平的 长随机数序列我可以翻阅 前后移动 .就像一台带有“下一个”和“上一个”按钮的机器，它会给你随机数。

诸如 10 位分辨率(即 0 到 1023 范围内的正整数)之类的东西就足够了，并且是一个 > 100k 数字的序列。这是一个简单的游戏类应用程序，我不需要加密强度随机性 或任何东西，但我希望它感觉相当随机。我有一个 内存有限虽然可用，所以我不能只生成一大块随机数据并通过它。我需要在“交互时间”中获取数字 - 我可以轻松地花几毫秒思考下一个数字，但不会比这更舒服。最终它将在某种微 Controller 上运行，可能只是一个 Arduino。

我可以用一个简单的线性同余生成器 (LCG) 来完成。前进很简单，要倒退，我必须缓存最近的数字并每隔一段时间存储一些点，以便我可以从那里重新创建序列。

但是也许有一些伪随机生成器可以让你同时前进和前进？应该可以连接两个线性反馈移位寄存器 (LFSR) 以向不同方向滚动，不是吗？

或者，也许我可以通过使用某种散列函数来弄乱索引号？我要先试试。

还有其他想法吗？

Answer 1

我问了 very similar question at the tigsource forums .

散列

至少在游戏中，散列函数可能可以做你想做的事。你可以这样做

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

可逆线性同余发生器 (lcg)

正如多人指出的那样，lcg 确实是可逆的。在 lcg 中，下一个状态是这样计算的:

x = (a * prevx + c) mod m

我们可以重新排序:

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

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

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 的周期

执行

我做了一个 header-only implementation of this algorithm万一有人感兴趣。