2

我将如何让 LCG（伪随机数发生器的类型）双向运行？我知道前进是(a*x+c)%m，但我怎么能扭转它？我正在使用它，因此我可以将种子存储在地图中玩家的位置，并能够通过在 LCG 中前后传播（如某种随机数轴）来生成围绕它的东西。

4

1 回答 1

3

所有 LCG 循环。在达到最大周期长度的 LCG 中，每个值 x 都有一个唯一的前任和一个唯一的后继（对于未达到最大周期长度的 LCG 或其他具有子周期行为的算法，例如 von Neumann 的中间平方方法）。

假设我们的 LCG 具有循环长度 L。由于行为是循环的，这意味着在 L 次迭代之后我们回到了起始值。通过后退一步找到前驱值在数学上等同于前移 (L-1) 步。

最大的问题是这是否可以转化为一个步骤。如果您使用的是素模乘法 LCG（加法常数为零），结果证明这很容易做到。如果 x i+1 = a * x i % m，则 x i+n = a n * x i % m。作为一个具体的例子，考虑 a = 16807 和 m = 2 31 -1 的 PMMLCG。它的最大循环长度为 m-1（由于显而易见的原因，它永远不会产生 0），所以我们的目标是迭代 m-2 次。我们可以使用现成的幂/模库预先计算m-2 % m = 1407677000。因此，向前一步是 x i+1 = 16807 * x i % 231 -1，而后退步骤为 x i-1 = 1407677000 * x i % 2 31 -1。

额外的

通过将转换转换为矩阵形式并进行快速矩阵求幂以得出等效的一阶段变换，可以将相同的概念扩展到通用的全周期 LCG。x i+1 = (a * x i + c) % m的矩阵公式为X i+1 = T · X i % m，其中 T 是矩阵[[a c],[0 1]]，X 是转置后的列向量 (x, 1)。通过使用平方和减半幂的快速取幂技术将 T 提高到任何所需的幂，可以快速计算 LCG 的多次迭代。在注意到矩阵 T 的幂永远不会改变第二行之后，我能够只关注第一行的计算，并在 Ruby 中生成了以下实现：

def power_mod(ary, mod, power)
  return ary.map { |x| x % mod } if power < 2
  square = [ary[0] * ary[0] % mod, (ary[0] + 1) * ary[1] % mod]
  square = power_mod(square, mod, power / 2)
  return square if power.even?
  return [square[0] * ary[0] % mod, (square[0] * ary[1] + square[1]) % mod]
end

其中ary是包含 a 和 c（乘法系数和加法系数）的向量。

将其power设置为循环长度 - 1，我能够确定产生Wikipedia 中列出的各种 LCG的前身的系数。例如，要“反转”具有 a = 1664525、c = 1013904223 和 m = 2 32的 LCG ，请使用 a = 4276115653 和 c = 634785765。您可以轻松确认后一组系数反转了使用原始系数。

于 2018-01-03T13:20:39.063 回答