C随机数生成(纯C代码，无库或函数)

Question

我需要在C中生成一些随机数来测试和调试系统。该系统是一个自定义硬件（SoC），功能有限，所以我只能使用基本的数学运算。

不，我不能在stdlib或math.h中使用随机数生成器。我需要自己写。那么，是否存在某种生成随机数的算法呢？

我知道一个简单的解决方案是在我的工作站上生成数字，并将它们嵌入到模块中，但我不想这样做。

Answer 1

只需挖掘Park和Miller在CACM 88年10月号上的文章。

他们提出的一般算法是：

a = 16807;
m = 2147483647;
seed = (a * seed) mod m;
random = seed / m;

尽管这篇文章包含了一些改进。

Answer 2

随机数生成器基本上是一个特殊的^*哈希函数，它从起始种子递归运行。

我在C#代码中使用了MurmurHash2算法，效果很好。它实现起来非常快速和简单，并且经过测试，分布非常均匀，碰撞率很低。该项目有几个用C++编写的不同的开源哈希函数，这些函数应该很容易转换为C.

---

^{*我的意思是，对一个值运行哈希函数应该返回另一个看似随机（但确定）的值，这样输出就不会形成模式。此外，返回值的分布应该是均匀的}

Answer 3

线性同余生成器实现起来很简单。这里提供了一个纯C语言的良好实现。

Answer 4

您可以尝试用George Marsaglia的进位相乘。

维基百科代码：

#include <stdint.h>
#define PHI 0x9e3779b9
static uint32_t Q[4096], c = 362436;
void init_rand(uint32_t x)
{
    int i;
    Q[0] = x;
    Q[1] = x + PHI;
    Q[2] = x + PHI + PHI;
    for (i = 3; i < 4096; i++)
            Q[i] = Q[i - 3] ^ Q[i - 2] ^ PHI ^ i;
}
uint32_t rand_cmwc(void)
{
    uint64_t t, a = 18782LL;
    static uint32_t i = 4095;
    uint32_t x, r = 0xfffffffe;
    i = (i + 1) & 4095;
    t = a * Q[i] + c;
    c = (t >> 32);
    x = t + c;
    if (x < c) {
            x++;
            c++;
    }
    return (Q[i] = r - x);
}

Answer 5

检查gsl库的源代码，其中实现了一些经过良好测试的算法。

Answer 6

您可能需要查找Mersenne Twister。有很多更高质量的算法。一篇很好的文章，概述你可以在这里找到：

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Answer 7

您可以尝试Isaac，它也可以作为CCAN的一部分在这里