生成全周期/全周期随机数或排列类似于 LCG 但没有奇/偶

发布于 2024-09-16 02:39:41 字数 941 浏览 9 评论 0原文

我希望生成“占据”某个范围内的整个周期或整个周期的伪随机数/排列。通常，“线性同余生成器”(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亿。
计算不应该发生溢出并且高效/快速，即：没有大指数或数十次乘法/除法。
序列不必非常随机或安全 - 我不需要加密随机性（但如果可行的话可以使用它），只需“良好”随机性或明显的随机性，没有奇数/偶数序列。

任何想法表示赞赏 - 提前致谢。

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

原文

I wish to generate psuedo-random numbers/permutations that 'occupy' a full period or full cycle within a range. Usually an 'Linear Congruential Generator' (LCG) can be used to generate such sequences, using a formula such as:

X = (a*Xs+c) Mod R

Where Xs is the seed, X is the result, a and c are relatively prime constants and R is the maximum (range).

(By full period/full cycle, I mean that the constants can be chosen so that any X will occur only once in some random/permuted sequence and will be within the range of 0 to R-1 or 1 to R).

LCG almost meets all of my needs. The problem I have with LCG is the non-randomness of the odd/even result, ie: for a seed Xn, the result X will alternate odd/even.

Questions:

Does anybody know how to create
something similar that will not
alternate odd/even?
I believe that a 'Compound LCG'
could be built, but I don't have
details. Can somebody give an
example of this CLCG?
Are there alternative formulas that
might meet the details above and
constraints below?

Constraints:

I want something based on a simple
seed-based formula. ie: to get the
next number, I provide the seed and
get the next 'random number' in
the permuted sequence. Specifically,
I cannot use pre-calculated arrays.
(See next points)
The sequence absolutely has to be 'full period/full cycle'
The range R could be several million
or even 32bit/4 billion.
The calculation should not suffer overflow and be efficient/fast, ie: no large exponents or dozens of multiplies/divides.
Sequence does not have to be terribly random or secure - I do not need cryptographic randomness (but can use it if viable), just 'good' randomness or apparent randomness, without odd/even sequences.

Any thoughts appreciated - thanks in advance.

UPDATE: Ideally the Range variable may not be an exact power of two, but should work in either case.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

面犯桃花 2024-09-23 02:39:58

在以下链接中，您可以找到组合 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

回复收藏 0 原文

九厘米的零° 2024-09-23 02:39:56

仅仅因为你不需要加密强度，并不意味着你不能借用密码学的一些想法......比如 Feistel 网络（Luby-Rackoff 构造）。

维基百科图片非常清楚。

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

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 的幂。

Just because you do not need cryptographic strength, that does not mean you cannot borrow some ideas from cryptography... Like the Feistel network (Luby-Rackoff construction).

The Wikipedia picture is pretty clear.

If you pick a simple and fast F -- it does not even need to guarantee unique output -- then you can just feed a sequence (0, 1, 2, ..., 2^n-1) to a few rounds of the Feistel network. Since the construction is reversible, this guarantees that the output never repeats.

Sample code for 32 bits:

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

You can mess around with the definition of F(), the number of rounds, etc. to suit your taste. The "full cycle" property is guaranteed no matter what you use there. In other words, if you have the loop in main go from 0 to 2^32-1, each 32-bit integer will occur once and only once, regardless of what you use for F or the number of rounds.

This does not exactly meet your stated requirement, since the input to gen_rand is not the "current random number"... The input is just the next integer. However, this does allow you to generate any element of the sequence at will (random access). And it is easy to invert if you really, really want to pass the "current random number" as input.

Pretty easy to adapt to different numbers of bits, although it does require that your R is a power of 2.

回复收藏 0 原文

客…行舟 2024-09-23 02:39:55

另一种简单、高效且易于理解的 PRNG 是线性反馈移位寄存器。按照本文中的步骤即可轻松实现完整周期。

编辑：

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

回复收藏 0 原文

是伱的 2024-09-23 02:39:53

排列同余生成器似乎具有您正在寻找的所有品质：

http://www.pcg-random.org< /a>

// *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++ 实现、更完整的 C 实现和 Haskell 实现。

Permuted congruential generators seem to have all the qualities you're looking for:

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

There are other varieties available at the website, including a C++ implementation intended to work with the <random> header (e.g., the distributions), a more complete C implementation, and a Haskell implementation.

回复收藏 0 原文

清风挽心 2024-09-23 02:39:50

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

编辑：

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

初始 LCG 的伪代码：

function rand
   state := update(state)
   return state

包括交换的 LCG 的伪代码：

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

If odd/even alternation is your only problem, leave the state change computation unchanged. Before using each output you can either shift the lower bits out or swap the the bits around.

Edit:

With the bit-swapping (fixed pattern) variant, you will keep generating whole periods.

Pseudo-Code of initial 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

回复收藏 0 原文

_畞蕅 2024-09-23 02:39:48

简单的解决方案。制作一个 LCG，其中 R 是一个比您想要的范围稍大的质数，并且 a 和 c 都在该范围内的某个随机位置。如果它给你的数字比你想要的大，请再次迭代，直到回到范围内。

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

如果您想要的范围很大，那么最接近的较大素数只会大一点，因此您很少需要调用它两次。例如，如果您所需的范围是十亿，则可以使用 1000000007 作为素数，并且您需要跳过少于 0.000001% 的时间的额外数字。

我通过访问 http://primes.utm.edu/curios/includes/ 找到了这个素数primetest.php 并输入数字，直到得到素数。我有点幸运。以 1, 3, 7, 9 结尾的 n 为素数的几率约为 2.5/log(n)，其中十亿为大约 12%，所以我很幸运，只尝试了 4 次就找到了这个数字。但没那么幸运 - 我在 3 次尝试中找到了它，平均我应该需要 8 次。

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