双向随机数生成器

Question

我需要一个不仅可重复的PRNG，还能够在两个方向上遍历其内部状态。

例如：

r = prng_from_seed(seed)
r.next # => 0.12332132412
r.next # => 0.57842057177
r.next # => 0.74782915912
r.prev # => 0.57842057177
r.next # => 0.74782915912

有哪些相对强大的 PRNG 算法具备这个特征？

- samuil

---

你需要这些类K3和K4吗？您的列表是K1和K2类的伪随机数生成器。==> https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_20_Functionality_Classes_Evaluation_Methodology_DRNG_e.pdf?__blob=publicationFile - SQL Police

浮点数存在精度问题。你确定不想使用无损的整型吗？ - Jongware

Answer 1

使用简单计数器作为种子，通过next增加并通过prev减少。然后使用此计数器作为另一个随机生成器的种子，以生成随机数。

- Ebbe M. Pedersen

---

值得注意的是，您可以使用某些块密码（带有固定的、可能是秘密的密钥，可以从初始种子派生）来加密计数器值，然后以某种方式将生成的（随机）块转换为输出数字，而不是使用另一个伪随机数生成器。 - vlp

Answer 2

有一些随机数生成器（RNG）具有快速的对数（log2（N））前向和后向跳跃功能（也称为跳跃）。它们基于F. Brown的论文“Random Number Generation with Arbitrary Stride”，Trans。美国核学会（1994年11月）。

比较简单的一个用于著名的MC代码MCNP中，Fortran和C++实现https://github.com/Iwan-Zotow/LCG-PLE63，尽管它无法通过像Diehard这样的测试。

更复杂但质量卓越的是PCG随机数族，位于http://www.pcg-random.org/。

- Severin Pappadeux

---

这太慢了。这个 https://dev59.com/3HE85IYBdhLWcg3wKwOE#16630535 不是快得多吗？ - happy_marmoset

Answer 3

几乎所有的伪随机数生成器都具有这个特性，但是从来没有人实现过回到先前状态的方法。

考虑以下情况：

由于伪随机数生成器具有有限大小的状态，重复调用next()最终会进入之前已经存在的状态。

如果您从将通过进行N次调用next()而最终到达的状态开始，则可以通过进行N-1次调用next()来找到前一个状态。

当然，在实际生活中，您希望实现prev()的方式更加高效。如何做取决于RNG，但通常并不太难。

请注意，为了最大限度地利用它们的状态，伪随机数生成器被设计为具有尽可能大的周期。通常，所有可访问的状态都在同一个周期中。

编辑：

我应该补充说，当人们在现实生活中想要做到这一点时，他们通常只使用计数器作为内部状态，并对其进行哈希（或使用固定密钥进行加密）以生成每个随机数。在密码上下文中，这称为“CTR MODE”加密，可以在Google上搜索到。

当然，如果您这样做，那么您可以随机访问每个状态。

- Matt Timmermans

---

但是没有人实现“转到上一个状态”方法。咦？请检查我的答案。 - Severin Pappadeux