制作可前后移动的可定制 LCG [英] Making a customizable LCG that travels backward and forward

问题描述

我将如何让 LCG(伪随机数发生器的类型)双向传播?我知道向前行驶是 (a*x+c)%m 但我如何才能逆转它?我正在使用它，因此我可以将种子存储在地图中玩家的位置，并能够通过在 LCG 中向后和向前传播来生成它周围的东西(就像某种随机数轴).

How would i go about making an LCG (type of pseudo random number generator) travel in both directions? I know that travelling forward is (a*x+c)%m but how would i be able to reverse it? I am using this so i can store the seed at the position of the player in a map and be able to generate things around it by propogating backward and forward in the LCG (like some sort of randomized number line).

推荐答案

所有 LCG 循环.在达到最大循环长度的 LCG 中，每个值 x 都有一个唯一的前驱和唯一的后继(对于没有达到最大循环长度的 LCG，或者对于其他具有子循环行为的算法，例如 vonNeumann 的中方法).

All LCGs cycle. In an LCG which achieves maximal cycle length there is a unique predecessor and a unique successor for each value x (which won't necessarily be true for LCGs that don't achieve maximal cycle length, or for other algorithms with subcycle behaviors such as von Neumann's middle-square method).

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

Suppose our LCG has cycle length L. Since the behavior is cyclic, that means that after L iterations we are back to the starting value. Finding the predecessor value by taking one step backwards is mathematically equivalent to taking (L-1) steps forward.

最大的问题是这是否可以转换为一个步骤.如果您使用的是质数乘法 LCG(其中加性常数为零)，结果证明很容易做到.如果 x_i+1 = a * x_i % m，则 x_i+n = aⁿ *x_i % m.作为一个具体的例子，考虑 a = 16807 和 m = 2³¹-1 的 PMMLCG.它的最大循环长度为 m-1(由于显而易见的原因，它永远不会产生 0)，因此我们的目标是迭代 m-2 次.我们可以使用现成的幂运算/mod 库预先计算 a^m-2 % m = 1407677000.因此，向前一步被发现为 x_i+1 = 16807 * x_i % 2³¹-1，而向后一步被发现x_i-1 = 1407677000 * x_i % 2³¹-1.

The big question is whether that can be converted into a single step. If you're using a Prime Modulus Multiplicative LCG (where the additive constant is zero), it turns out to be pretty easy to do. If x_i+1 = a * x_i % m, then x_i+n = aⁿ * x_i % m. As a concrete example, consider the PMMLCG with a = 16807 and m = 2³¹-1. This has a maximal cycle length of m-1 (it can never yield 0 for obvious reasons), so our goal is to iterate m-2 times. We can precalculate a^m-2 % m = 1407677000 using readily available exponentiation/mod libraries. Consequently, a forward step is found as x_i+1 = 16807 * x_i % 2³¹-1, while a backwards step is found as x_i-1 = 1407677000 * x_i % 2³¹-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).LCG 的多次迭代可以通过使用平方和减半幂的快速取幂技术将 T 提高到任何所需的幂来快速计算.在注意到矩阵 T 的幂永远不会改变第二行之后，我能够只关注第一行的计算并在 Ruby 中生成以下实现:

The same concept can be extended to generic full-cycle LCGs by casting the transition in matrix form and doing fast matrix exponentiation to come up with the equivalent one-stage transform. The matrix formulation for x_i+1 = (a * x_i + c) % m is X_i+1 = T · X_i % m, where T is the matrix [[a c],[0 1]] and X is the column vector (x, 1) transposed. Multiple iterations of the LCG can be quickly calculated by raising T to any desired power through fast exponentiation techniques using squaring and halving the power. After noticing that powers of matrix T never alter the second row, I was able to focus on just the first row calculations and produced the following implementation in 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(乘法和加法系数)的向量.

where ary is a vector containing a and c, the multiplicative and additive coefficients.

使用它并将 power 设置为周期长度 - 1，我能够确定产生 维基百科中列出的各种 LCG.例如，要使用 a = 1664525、c = 1013904223 和 m = 2³²反转"LCG，请使用 a = 4276115653 和 c = 634785765.您可以轻松确认后一组系数反转使用原始系数产生的序列.

Using this with power set to the cycle length - 1, I was able to determine coefficients which yield the predecessor for various LCGs listed in Wikipedia. For example, to "reverse" the LCG with a = 1664525, c = 1013904223, and m = 2³², use a = 4276115653 and c = 634785765. You can easily confirm that the latter set of coefficients reverses the sequence produced by using the original coefficients.

这篇关于制作可前后移动的可定制 LCG的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！