rand()的实现

Question

我正在使用C语言编写嵌入式代码，并需要使用rand()函数。不幸的是，控制器的库不支持rand()。我需要一个简单的实现，它要快速运行，但更重要的是具有较小的空间开销，能够产生相对高质量的随机数。有人知道应该使用哪个算法或有示例代码吗？

编辑：这是用于图像处理的，因此“相对高质量”的意思是具有不错的周期长度和良好的均匀性。

- rlbond

---

你具体需要什么？需要长周期长度吗？我们说的数字有多大（16位、32位或其他）？它们需要多随机？“空间开销”是指ROM限制，RAM限制还是两者都包括？ - David Thornley

如果您有一个SysTick或其他可以用于从上电到当前时间计时的东西，那么您可以将该计数器用作下面显示的某些随机生成器的种子。 - avra

这是一个C++类中Mersenne Twister的实现。 - bobobobo

Answer 1

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

Marsaglia的生成器在您对长周期和良好均匀分布的标准下确实是“高质量”的。它们通过了严格的统计测试，但不适用于加密。

- John D. Cook

---

谢谢您提供的参考资料。我做了一些调查，并发现Greg Rose的“KISS: a Bit Too Simple”（http://eprint.iacr.org/2011/007.pdf）警告了MWC中“坏”种子值，并对SHR3生成器表示怀疑。 Marsaglia在2003年发布的这篇文章（http://groups.google.com/group/sci.math/msg/9959175f66dd138f）提供了一个略有不同但可以解决早期问题的SHR3。只要检查和避免“坏”种子并确保使用更好的SHR3生成器，我将很乐意使用KISS-style生成器。 - Craig McQueen

Marsaglia在90年代对PRNG做出了重大贡献，但今天我可能会选择L'Ecuyer或Matsumoto。话虽如此，如果OP在嵌入式设备上不进行主要模拟，那么早期的好发生器大多数也可以使用 :-) - Joey

@Joey: Marsaglia的KISS生成器在L'Ecuyer的TestU01 RNG测试中表现良好，甚至通过了一些L'Ecuyer自己的RNG（如LFSR113）未能通过的测试。 - Craig McQueen

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()函数，它比无用更糟糕。

- R Simard

---

请注意，这假定了一个32位的整数，这可能不适合嵌入式平台。 - tomlogic

为什么这个是随机的？ - me me

我觉得这要看你所说的“随机”是什么意思。LFSR RNG基于明确定义的数学递归，具有已知周期和良好的统计特性（被认为是随机的）。除非你从某些物理现象（例如线路噪声）中获取熵，否则你使用的任何RNG都将类似伪随机。（加密安全的RNG更复杂，但仍然是伪随机的）。更强大的Mersenne Twister是一个扭曲的GFSR，因此与上述相关，而较弱的Xorshift是LFSR的一种特殊情况。CMWC RNG可以比它们中的任何一种都更快且更强大。 - Mike S

@我：它是伪随机数，静态变量保存种子值。它总是返回相同的数字序列。 - k3a

把种子设为静态变量可能是个错误，但这看起来很有前途，只要确保在外部提供种子就可以了。我会尝试一下。至于32位，实际的源代码使用uint32_t而不是unsigned int，所以也不应该是个问题。 - AlexKven

在看了一些资料并进行了谷歌搜索后，我发现了https://github.com/cmcqueen/simplerandom，这似乎是本答案作者的有用随机函数集合！ 其中我看到了这个注释，它与使用的种子相关（最初看起来有点可疑） /**** 非常重要 ****： 初始种子z1、z2、z3、z4必须大于1、7、15和127。 */ 如果您计划更改种子值，则此注释非常有用！ - simap

Answer 3

这里有一个 ANSI C 随机数生成器的实现链接。

- Reed Copsey

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周期，这是此生成器的总周期。

我发现了一些关于种子的问题，并尝试制定强大的种子初始化程序，以便它们不会在给出“错误”的种子值时中断。

- Craig McQueen

---

这是一篇较旧的文章，但我想进行更正：Marsaglia的2x16 MWC生成器的低16位实际上似乎具有589823999 = 2^29.1357092836584的周期，而不是2^16。（这是可能的，因为状态包括进位共有32位。）周期是b mod p的阶，其中b = 2^16，p = 18000 * 2^16 - 1。在这种情况下，阶= 589823999 =（p-1）/ 2。使用基于65536的MWC和16位乘法器，您可以做到最好的周期是65495，其周期为2^30.9990971519312。最好的安全质数是65184，给出了2^30.9922302642905的周期。 - Mike S

Marsaglia的2x16 MWC生成器的高位具有1211400191 = 2^30.1740283979574的周期，低位具有589823999 = 2^29.1357092836584的周期。两者的连接周期为714512905044983809 = 2^59.3097376816159，但是单独的高位和低位仍然具有独立的低周期。您修改后的MWC2可以提高低位输出质量，而不会破坏底层生成器的数学基础，使低位的周期与总组合相同，并且也有助于高位...但我不确定提高了多少。 - Mike S

是的，你说得很对。我说MWC低16位只有2^16个周期，但我应该说是2^29.1个周期。我已经相应地进行了编辑。但我不认为我在MWC2中的更改会对高位产生任何影响。 - Craig McQueen

你所做的更改对高位的影响是微妙的：当你加上高位和低位时，有时会将另一个1位进位到高位，从而略微改变高位约一半的时间。实际上，我在高位周期方面是错误的：我说它们具有独立的2^30.1740283979574周期，但实际上它们具有完整的2^59.3097376816159周期，因为Marsaglia已经通过添加znew的低16位和wnew的高16位来构造它们。我一开始没有注意到后者。 - Mike S

我原本以为你的更改会帮助高位和低位的周期（随机性不太重要），但由于高位已经有了完整的周期，所以并不重要。实际上，在我最后一条评论中，我又犯了一个错误：进位的1位发生的次数远远少于一半的时间...只是偶尔发生。顺便说一句，很高兴你能用MWC找到额外的坏种子。不过有点可怕的是，它们似乎没有符合其他MWC生成器的明显模式... - Mike S

Answer 5

梅森旋转算法

维基百科上的一些信息:

• 该算法被设计为具有2¹⁹⁹³⁷ − 1的周期（该算法的创建者证明了这个属性）。实际上，大多数应用程序不需要使用更大的周期，因为它们并不需要2¹⁹⁹³⁷个唯一组合（2¹⁹⁹³⁷约为4.3×10⁶⁰⁰¹；这比可观测宇宙中估计的粒子数量10⁸⁰要大得多）。
• 它具有非常高的维度等分布阶数（参见线性同余生成器）。这意味着输出序列中相邻值之间几乎没有串行相关性。

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

• 许多语言的源代码可以在链接中找到。

- Liran Orevi

Answer 6

我推荐David Carta的学术论文 《最小标准随机数生成器的两个快速实现》。你可以通过谷歌免费获取PDF版本。原始论文也值得一读。

Carta的代码可以在32位计算机上快速生成高质量的随机数。如需更详细的评估，请参阅该论文。

- Norman Ramsey

Answer 7

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

假设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;
}

- BenW

Answer 8

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

http://qa.coreboot.org/docs/libpayload/rand_8c-source.html

但是，如果您对随机数的质量有任何疑虑，您可能应该更仔细地查看编写得更好的数学库。这是一个大课题，标准的rand实现并不受专家们的高度评价。

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

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

- Daniel Earwicker

---

rand.c源代码链接似乎已经失效。请尝试使用rand.c和random.c的git仓库。 - Craig McQueen

请注意，代码将受GPL或LGPL的约束。始终了解您源代码的许可证。 - davenpcj

Answer 9

我找到了这个：简单的随机数生成，作者是John D. Cook。

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

编辑：你可以澄清一下“相对高质量”的含义吗？你是为核弹发射代码生成加密密钥，还是为打扑克游戏生成随机数？

- erjiang

---

这是由John D. Cook所写的，他在那个答案中提到了基于Marsaglia帖子的方法。 - Craig McQueen

Answer 10

有一个简单的 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; 
}

还有一个网站可以测试随机数生成器http://www.phy.duke.edu/~rgb/General/dieharder.php

- zangw