生成与LCG相似但没有奇/偶数的全周期/全循环随机数或排列

Question

我希望生成psuedo-随机数/排列，“占据”一个完整的周期或在一个范围内的完整循环。通常可以使用“线性同步器”(LCG)来生成这样的序列，使用如下公式：

X = (a*Xs+c) Mod R

Xs是种子，X是结果，a和c是相对素常数，R是最大(范围)。

(完整周期/全周期，我的意思是可以选择常数，使任何X在某些随机/置换序列中只发生一次，并且在0到R-1或1到R的范围内)。

LCG几乎满足了我所有的需求。我对LCG的问题是奇/偶数结果的非随机性，即对于种子Xn，结果X将交替奇偶。

问题：

1. 有没有人知道如何创建类似的东西而不会交替使用奇数/偶数？
2. 我相信可以建造一个‘复合LCG’，但我不知道细节。谁能举个这个CLCG的例子吗？
3. 是否有其他公式可以满足上述细节和下面的限制？

Constraints:

1. 我想要一个简单的基于种子的公式。为了得到下一个数字，我提供种子，并在排列序列中得到下一个“随机数”。具体来说，我不能使用预先计算的数组.(见下几点)
2. 序列绝对必须是“全周期/全周期”。
3. R的范围可以是几百万甚至32位/40亿。
4. 计算不应该有溢出，而且是有效的/快速的，即:没有大的指数或几十个乘法/除法。
5. 序列不必是非常随机或安全的-我不需要密码随机性(但可以使用它，如果可行)，只是‘好的’随机性或表面随机性，没有奇数/偶数序列。

任何想法都很感激--谢谢。

更新:理想情况下，范围变量可能不是2的确切幂，但在这两种情况下都应该工作。

Answer 1

琐碎的解将带有R的LCG设置为一个比您想要的范围稍大的素数，并且a和c在该范围内的某个地方都是随机的。如果它给了你一个比你想要的更大的数字，再次迭代，直到你回到你的范围。

数字输出将不会有一个特别简单的模式mod 2，3，5等，直到任何素数小于您使用的素数。

如果你想要的范围很大，那么最近的更大的质数只会变大，所以你很少需要调用它两次。例如，如果您想要的范围是十亿，您可以使用1000000007作为您的质数，您需要跳过一个额外的数字少于0.000001%的时间。

我找到这个质数的方法是去http://primes.utm.edu/curios/includes/primetest.php，然后输入数字，直到得到质数。我有点幸运。以n结尾的1, 3, 7, 9是素数的概率大约是2.5/log(n)，在10亿的时候大约是12%，所以我很幸运地在4次尝试后就找到了这个数字。但没那么幸运--我在三次尝试中就发现了，平均来说我应该需要8次。

编辑：这个随机数生成器可以有一个较短的周期。见@dzugaru的说明。

Answer 2

如果奇数/偶数交替是您唯一的问题，则状态更改计算保持不变。在使用每个输出之前，您可以将较低的位移出或交换周围的位。

编辑：

使用位交换(固定模式)变体，您将继续生成整个周期.

初始LCG伪码：

function rand
   state := update(state)
   return state

包括交换在内的LCG伪代码：

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state

Answer 3

置换同余生成器似乎具有您要寻找的所有特性：

http://www.pcg-random.org

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

网站上还有其他种类，包括一个用于处理C++头(例如发行版)的<random>实现、一个更完整的C实现和一个Haskell实现。