生成类似于LCG但不包含奇偶数的完整周期/完整循环随机数或排列

Question

生成类似于LCG但不包含奇偶数的完整周期/完整循环随机数或排列

11

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

X = (a*Xs+c) Mod R

在此，Xs为种子，X为结果，a和c是互质的常数，R为最大值（范围）。

（通过完全周期/循环，我指的是可以选择常数，使得任何X仅在某个随机/混合序列中出现一次，并且将在范围0到R-1或1到R内。）

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

问题：

有人知道如何创建类似的东西，不会交替奇/偶吗？
我相信可以构建'复合LCG'，但我没有细节。有人可以给出这个CLCG的例子吗？
是否有其他公式可以满足上述细节和约束条件？

限制条件：

我希望基于简单的基于种子的公式。即：要获得下一个数字，我提供种子并获得排列序列中的下一个“随机数”。具体来说，我不能使用预先计算的数组。（请参见下一个点）
序列绝对必须是“完全周期/循环”
范围R可以是几百万甚至32位/ 40亿。
计算不应遭受溢出，并且应高效/快速，即没有大的指数或十几个乘除运算。
序列不必非常随机或安全-我不需要密码随机性（但如果可行，则可以使用它），只需“好”的随机性或明显的随机性，而无奇/偶序列。

任何想法都受到赞赏-提前感谢。

更新：理想情况下，范围变量可能不是2的幂，但在任一情况下都应起作用。

- andora

昨天有一个非常类似的问题被发布了，也许会对你有兴趣。https://dev59.com/e1DTa4cB1Zd3GeqPFwug#3575618 - Dr. belisarius

非常相似。谢谢您提供的链接。 - andora

1

你为什么创建了悬赏？Peter G的解决方案没有提供什么你在寻找的吗？如果你需要更多的东西，应该在某个地方具体说明。 - Fantius

@Fantius：我多次回顾了这个问题，但并没有找到一个足够简洁/优雅的解决方案。我也没有想到比特位交换可能会产生解决方案。现在经过详细考虑，我认为这是可能的。但是，我认为移位不是一个好的选择。奖励确实带来了一些额外的见解（感谢@btilly），但在接受答案之前，我仍然希望探索和测试其他可能性。 - andora

6个回答

3

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

编辑：

使用位交换（固定模式）变体，您将继续生成整个周期。

初始LCG的伪代码：

function rand
   state := update(state)
   return state

Pseudo-Code of LCG including swapping:

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

- Peter G.

可以的！足够简单和容易，我会试一下。谢谢。 - andora

我认为为了实现随机性，只需进行位移，您的位移量本身应该是随机的。因此，您需要两个“解耦”的随机生成器。 - Dr. belisarius

2

不确定这是否明智，因为我很可能会失去序列的“完整周期”排列属性。生成完整周期序列是一个严格的约束条件。 - andora

是的，你可以这样做。按照Peter G的建议，交换LCG输出的两个部分以形成新的输出。 - Fantius

我不确定我是否理解第一句话：“状态改变计算不变”？现在我明白了，位交换过程将无论如何保留完整的循环属性。感谢您的帮助+1。 - andora

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));
}

网站上还有其他种类的实现，包括一个用于与<random>头文件一起使用（例如分布）的C++实现，一个更完整的C实现和一个Haskell实现。

- bames53

2

只因您不需要加密强度，并不意味着您不能从加密中借鉴一些思想，比如 Feistel 网络（Luby-Rackoff 构造）。维基百科图片非常清晰。

如果您选择一个简单而快速的 F —— 它甚至不需要保证唯一输出 —— 那么您可以将序列 (0, 1, 2, ..., 2^n-1) 输入到几轮 Feistel 网络中。由于构造是可逆的，这保证了输出永远不会重复。

32 位示例代码：

#include <stdint.h>
#include <stdio.h>

/* Just some fixed "random" bits... */
union magic {
    double d;
    uint16_t n[4];
};

const union magic bits = { 3.141592653589793238462643383 };

static uint16_t
F(uint16_t k, uint16_t x)
{
    return 12345*x + k;
}

static uint32_t
gen_rand(uint32_t n)
{
    uint16_t left = n >> 16;
    uint16_t right = n & ((1UL << 16) - 1);

    for (unsigned round=0 ; round < 4 ; ++round) {
        const uint16_t next_right = left ^ F(bits.n[round], right);
        const uint16_t next_left = right;
        right = next_right;
        left = next_left;
    }

    return (((uint32_t)left) << 16) + right;
}

int
main(int argc, char *argv[])
{
    for (uint32_t n = 0 ; n < 10 ; ++n) {
        printf("gen_rand(%lu) == %08lx\n", (unsigned long)n,
               (unsigned long)gen_rand(n));
    }
    return 0;
}

您可以随意更改F（）的定义，轮数等以适应您的口味。无论您在那里使用什么，都可以保证“完整周期”属性。换句话说，如果您在main中的循环从0到2 ^ 32-1，每个32位整数将只出现一次，无论您用于F或轮数如何。

这并不完全满足您所述的要求，因为gen_rand的输入不是“当前随机数”...输入只是下一个整数。但是，这确实允许您随意生成序列中的任何元素（随机访问）。如果您真的非常想将“当前随机数”作为输入传递，那么也很容易反转。

很容易适应不同位数，尽管它需要您的R是2的幂。

- Nemo

感谢您的回答。虽然R可能是2的幂，但我更喜欢不必要求它是这样的可能性。我熟悉这个解决方案，但如果其他解决方案更容易实现，我会犹豫重新设计它，比如对于一个24位数字。然而，“输入”种子并不是问题，如果需要，我也不需要反转这个过程，但我意识到我可以这样做。 - andora

2

另一个易于理解、高效的 PRNG 是线性反馈移位寄存器。按照文章中的步骤很容易实现完整周期。

编辑：

您可能考虑使用为格式保留加密开发的一些技术。我相信这些技术可以很容易地适应生成排列的需求。

- President James K. Polk

我之前考虑过LFSR甚至Fibonacci LFSR，但由于某些原因被排除在外，现在忘记了。Belisarius回答了这里链接的SO问题，并提出了一种处理二进制范围限制的方法，所以我会再看一眼。唯一的问题是，你确定它可以处理奇偶问题吗？另一个问题是“锁定”，但我认为这只在硬件实现时才真正重要。感谢您的建议。 - andora

@andora 是的...对于斐波那契数列并没有奇偶规律（请参考我在另一个问题中回答中链接到的维基百科示例）。 - Dr. belisarius

@andorra：可能您反对是因为这个周期必须是2 ** n - 1的形式？ - President James K. Polk

有点像：我真的希望保持“完整循环”属性，因为我想生成一个排列集。修剪结果以实现非二进制范围是有问题的。例如：假设我想将1到9进行“排列”，以获得5,1,8,2,3,6,9,4,7。对于15/16的二进制范围，我必须重复调用，直到结果落在区间内。这里并不是什么大问题，但对于32位/40亿的大范围来说，可能需要成千上万次调用，直到结果落在范围内。 - andora

1

在下面的链接中，您可以找到一个结合的LCG示例。（包括文档和源代码）（注意：算法是开放的，但源代码的许可证不是开放的（即没有派生代码））

http://resource.npl.co.uk/docs/science_technology/scientific_computing/ssfm/documents/wh_rng_version096.zip

你甚至可以尝试这个7阶XORshift RNG示例：

https://gist.github.com/709285

- jj1bdx

感谢您的帮助 - 非常感激。 - andora

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

简单的解决方案。制作一个LCG，其中R是略大于你想要的范围的素数，a和c都在该范围内随机选择。如果产生的数字比您想要的范围大，则迭代直到回到范围内。

输出的数字对于小于使用的素数的任何质数模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次后就找到了这个数字，有点幸运。但是不算太幸运-我在3次尝试中找到了它，平均需要8次。

编辑：这个随机数生成器可能具有较短的周期。请参见@dzugaru的注释。