rand() 的实现

Question

我正在用 C 编写一些嵌入式代码，需要使用 rand() 函数。 不幸的是，控制器的库不支持 rand()。 我需要一个快速的简单实现，但更重要的是空间开销很小，可以产生相对高质量的随机数。 有谁知道使用哪种算法或示例代码？

编辑：它用于图像处理，因此“相对高质量”意味着良好的周期长度和良好的均匀特性。

Answer 1

查看 George Marsaglia 的随机数生成器集合。 他是随机数生成方面的领先专家，因此我有信心使用他推荐的任何内容。 该列表中的生成器很小，有些只需要几个无符号长整型作为状态。

按照长期使用和良好均匀分布的标准，Marsaglia 的发电机绝对是“高品质”的。 它们通过了严格的统计测试，尽管它们不适用于密码学。

Answer 2

使用C 代码作为来自 L'écuyer 的 LFSR113：

unsigned int lfsr113_Bits (void)
{
   static unsigned int z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345;
   unsigned int b;
   b  = ((z1 << 6) ^ z1) >> 13;
   z1 = ((z1 & 4294967294U) << 18) ^ b;
   b  = ((z2 << 2) ^ z2) >> 27; 
   z2 = ((z2 & 4294967288U) << 2) ^ b;
   b  = ((z3 << 13) ^ z3) >> 21;
   z3 = ((z3 & 4294967280U) << 7) ^ b;
   b  = ((z4 << 3) ^ z4) >> 12;
   z4 = ((z4 & 4294967168U) << 13) ^ b;
   return (z1 ^ z2 ^ z3 ^ z4);
}

非常高的质量和速度。 不要将 rand() 用于任何事情。
这比无用更糟糕。

Answer 3

这是 ANSI C 一些随机数生成器的实现的链接。

Answer 4

我制作了一系列随机数生成器“simplerandom”，它们结构紧凑，适合嵌入式系统。 该集合可在 C 和 Python。

我四处寻找一些我能找到的简单而体面的东西，并将它们放在一个小包中。 它们包括几个 Marsaglia 生成器（KISS、MWC、SHR3）和几个 L'Ecuyer LFSR 生成器。

所有生成器都返回一个无符号 32 位整数，并且通常具有由 1 到 4 个 32 位无符号整数组成的状态。

有趣的是，我发现了 Marsaglia 生成器的一些问题，并且我尝试修复/改进所有这些问题。 这些问题是：

• SHR3 发电机（Marsaglia 1999 KISS 发电机的组件）损坏。
• MWC 低 16 位只有大约 2^29.1 周期。 所以我做了一个稍微改进的MWC，它给低16位一个2^59.3周期，这是这个发生器的整体周期。

我发现了一些有关播种的问题，并尝试制定强大的播种（初始化）程序，因此如果您给它们一个“坏”种子值，它们就不会中断。

Answer 5

我推荐学术论文最小标准随机数生成器的两种快速实现大卫·卡尔塔. 您可以通过 Google 找到免费的 PDF。 关于最小标准随机数生成器的原始论文也值得一读。

Carta 的代码在 32 位机器上提供快速、高质量的随机数。 如需更全面的评估，请参阅论文。

Answer 6

梅森扭曲器

来自维基百科的一点信息：

• 它的设计周期为 2¹⁹⁹³⁷ - 1（算法的创建者证明了这个属性）。 实际上，没有理由使用更大的周期，因为大多数应用程序不需要 2¹⁹⁹³⁷ 个唯一组合（2¹⁹⁹³⁷ 约为 4.3 × 10^{6001< /sup>；这比可观测宇宙中的估计粒子数量（1080）大很多数量级。}
• 它具有非常高阶的维度均分布（参见线性同余生成器）。 这意味着输出序列中的连续值之间的序列相关性可以忽略不计。

• 它通过了许多统计随机性测试，包括 Diehard 测试。 它通过了大多数（但不是全部）更严格的 TestU01 Crush 随机性测试。

• 链接上提供了多种语言的源代码。

Answer 7

我会从 GNU C 库中获取一个，源代码可以在线浏览。

http://qa.coreboot.org/docs/libpayload/rand_8c-source。 但是，

如果您对随机数的质量有任何担忧，您可能应该查看更仔细编写的数学库。 这是一个很大的主题，专家们并没有高度重视标准的 rand 实现。

这是另一种可能性： http://www.boost.org/ doc/libs/1_39_0/libs/random/index.html

（如果您发现有太多选项，您可以随时随机选择一个。）

Answer 8

我发现了这个：简单随机数生成，作者：John D.做饭。

鉴于它只有几行代码，应该很容易适应 C。

编辑：您可以澄清“相对高质量”的含义。 您是否正在为核发射代码生成加密密钥，或者为扑克游戏生成随机数？

Answer 9

更好的是，使用多个线性反馈移位寄存器将它们组合在一起。

假设sizeof(unsigned) == 4：

unsigned t1 = 0, t2 = 0;

unsigned random()
{
    unsigned b;

    b = t1 ^ (t1 >> 2) ^ (t1 >> 6) ^ (t1 >> 7);
    t1 = (t1 >> 1) | (~b << 31);

    b = (t2 << 1) ^ (t2 << 2) ^ (t1 << 3) ^ (t2 << 4);
    t2 = (t2 << 1) | (~b >> 31);

    return t1 ^ t2;
}

Answer 10

标准解决方案是使用线性反馈移位寄存器。

Answer 11

有一个简单的RNG，名为KISS，它是根据三个数字生成一个随机数生成器。

/* Implementation of a 32-bit KISS generator which uses no multiply instructions */ 

static unsigned int x=123456789,y=234567891,z=345678912,w=456789123,c=0; 

unsigned int JKISS32() { 
    int t; 

    y ^= (y<<5); y ^= (y>>7); y ^= (y<<22); 

    t = z+w+c; z = w; c = t < 0; w = t&2147483647; 

    x += 1411392427; 

    return x + y + w; 
}

还有一个测试 RNG 的网站 http://www.phy.duke .edu/~rgb/General/dieharder.php