c - 8位单片机生成伪随机数最快的方法是什么？

Question

Linear congruential generator是一个很好的算法。但是有没有更快的算法呢？

Answer 1

我记得，8051有一个 8x8=16 位乘法器，因此实现滞后 n multiply-with-carry 可能是可行的发电机。这种技术的好处是，如果你能找到一个合适的安全素数，你可以用很少的运算得到一个很长的周期。

不幸的是，似乎没有太多带有只有八位乘数的安全素数选项，我担心较短的乘数可能会导致一些通常不会出现在 MWC 中的弱点。

我只是把它放在一起，虽然我不能 100% 确定它正确地实现了 MWC，但它实际上通过了惊人数量的 dieharder测试:

#define STATE_BYTES 7
#define MULT 0x13B /* for STATE_BYTES==6 only */
#define MULT_LO (MULT & 255)
#define MULT_HI (MULT & 256)

uint8_t rand8(void)
{
    static uint8_t state[STATE_BYTES] =
    { 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c };
    static uint16_t c = 0x42;
    static int i = 0;
    uint16_t t;
    uint8_t x;

    x = state[i];
    t = (uint16_t)x * MULT_LO + c;
    c = t >> 8;
#if MULT_HI
    c += x;
#endif
    x = t & 255;
    state[i] = x;
    if (++i >= sizeof(state))
        i = 0;
    return x;
}

如您所见，乘法器实际上是九位，但我们使用移位加法来实现硬件乘法器无法管理的最后一位。

在进一步测试中，我发现了一个合适的 89 位安全素数，它确实通过了几乎所有的顽固分子测试。更改这些行:

#define STATE_BYTES 10
#define MULT 0x153 /* for STATE_BYTES==10 only */

我用这个种子进行测试:

static uint8_t state[STATE_BYTES] =
{ 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c, 0xb6, 0xca, 0x0a, };
static uint16_t c = 0x42;

种子只是/dev/random 中的一些位，您可以自由选择自己的。然而，增加状态大小基本上是作弊，因为它允许种子的质量在随机性测试的成功或失败中发挥更大的作用。坏种子可能会导致不是很随机的结果。