rand()的实现

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

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

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

按照您的长期标准和良好的均匀分布,Marsaglia的发电机绝对是“高品质”。 他们通过严格的统计测试,但他们不会做密码学。

使用L’écuyer的LFSR113 的C代码 :

 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()做任何事情。 它比无用还糟糕。

这是一个指向几个随机数生成器的ANSI C 实现的链接。

我已经制作了一组随机数生成器,“ 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周期,这是这个发生器的整个周期。

我发现了一些播种问题,并尝试进行强大的播种(初始化)程序,因此如果你给它们一个“糟糕的”种子值,它们就不会破坏。

我推荐David Carta的学术论文“最小标准随机数发生器的两个快速实现” 。 您可以通过Google找到免费的PDF。 关于最小标准随机数发生器的原始论文也值得一读。

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

Mersenne twister

维基百科:

  • 它的设计周期为2 19937 – 1(算法的创建者certificate了这个属性)。 在实践中,几乎没有理由使用更长的时间段,因为大多数应用程序不需要2 19937个独特组合(2 19937约为4.3×10 6001 ;这比可观察宇宙中的估计粒子数大许多个数量级) ,这是10 80 )。
  • 它具有非常高的维度等分布(参见线性同余生成器)。 这意味着输出序列中连续值之间的序列相关性可忽略不计。
  • 它通过了许多统计随机性测试,包括Diehard测试。 它通过了大多数(但不是全部)更严格的TestU01 Crush随机性测试。

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

我从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

(如果您发现有太多选项,您可以随时选择一个。)

我发现了这个: 简单的随机数生成 ,由约翰D.库克 。

应该很容易适应C,因为它只有几行代码。

编辑:你可以用“相对高质量”来澄清你的意思。 您是否为核发射代码生成加密密钥,或者为扑克游戏生成随机数?

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

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

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

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

 /* 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