生成与LCG相似但没有奇偶的全周期/全周期随机数或置换

琐碎的解决方案。制作液晶显示器 R a 和 c

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

我是通过 http://primes.utm.edu/curios/includes/primetest.php 在我得到一个素数之前输入数字。我有点幸运。可能性 n 结束于 1, 3, 7, 9 质数大约是 2.5/log(n) 10亿是12%,所以我有点幸运,在4次尝试后找到了这个数字。但没那么幸运——我试了3次就找到了,平均下来我应该需要8次。

编辑:

编辑:

初始LCG伪码:

function rand
   state := update(state)
   return state

包括交换的LCG伪码:

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

另一个简单、高效、理解力强的PRNG是 Linear Feedback Shift Register . 按照本文中的步骤很容易实现完整周期。

你可以考虑一些为 Format-Preserving Encryption . 我相信这些可以很容易地适应产生排列。

仅仅因为你不需要密码强度,这并不意味着你不能从密码学中借鉴一些想法。。。比如Feistel网络(Luby Rackoff建筑)。

Wikipedia picture 很清楚。

如果你选择一个简单而快速的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的幂。

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

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> header(例如,发行版)、更完整的C实现和Haskell实现。

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