10

我希望生成在一个范围内“占据”一个完整周期或完整周期的伪随机数/排列。通常可以使用“线性同余生成器”（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. 是否有可能满足上述细节和以下限制的替代公式？

约束：

  1. 我想要一些基于简单种子公式的东西。即：要获得下一个数字，我提供种子并获得置换序列中的下一个“随机数”。具体来说，我不能使用预先计算的数组。（见下一点）
  2. 序列绝对必须是“全周期/全周期”
  3. 范围R可能是几百万甚至32bit/40亿。

  4. 计算不应溢出并且高效/快速，即：没有大指数或数十个乘法/除法。

  5. 序列不必非常随机或安全 - 我不需要加密随机性（但如果可行的话可以使用它），只需“良好”随机性或明显随机性，没有奇数/偶数序列。

任何想法表示赞赏 - 在此先感谢。

更新：理想情况下，范围变量可能不是 2 的精确幂，但在任何一种情况下都应该有效。

4

6 回答 6

10

微不足道的解决方案。制作一个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 次尝试后找到了这个数字。但没那么幸运——我在 3 次尝试中找到了它，平均而言我应该需要 8 次。

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

于 2011-06-10T01:50:36.803 回答
3

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

编辑：

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

初始 LCG 的伪代码：

function rand
   state := update(state)
   return state

LCG的伪代码，包括交换：

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state
于 2010-08-27T11:48:42.197 回答
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 实现。

于 2015-03-03T08:35:14.777 回答
2

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

编辑：

您可能会考虑为Format-Preserving Encryption开发的一些技术。我相信这些可以很容易地适应产生排列。

于 2010-08-27T12:13:11.317 回答
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 的幂。

于 2011-06-15T21:35:33.350 回答
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

于 2010-12-12T01:37:04.147 回答