What is the fastest way to generate pseudo random number by 8-bit MCU?

Question

Linear congruential generator is a good algorithm. But is there any faster algorithm?

Answer 1

As I recall, 8051 has an 8x8=16-bit multiplier, so it might be feasible to implement a lag-n multiply-with-carry generator. The advantage of this technique is that if you can find a suitable safe prime, you can get a very long period with very little arithmetic.

Unfortunately, there don't seem to be an awful lot of safe-prime options with a multiplier that is only eight bits, and I fear the short multiplier may result in some weaknesses that don't normally show up with MWC.

I just knocked this together, and while I'm not 100% certain it implements MWC correctly, it actually passes a surprising number of dieharder tests:

#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;
}

As you can see, the multiplier is actually nine bits, but we use a shift-and-add to implement that last bit which the hardware multiplier can't manage.

On further testing, I've found a suitable safe prime of 89 bits which does pass almost all of dieharder. Change these lines:

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

and I used this seed for testing:

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

The seed is just some bits from /dev/random, and you're free to choose your own. However, increasing the state size is basically cheating, because it allows the quality of the seed to play a greater role in the success or failure in randomness tests. It may be that bad seeds could result in not-very-random results.

Answer 2

Since 8-bit CPUs typically can't do fast division or even multiplication, it is often not a good idea to use a linear congruential generator.

Linear feedback shift register (LFSR) uses only shift and logical operations.

If you use an array it becomes the Generalized Linear Feedback Shift Register (GLFSR), the general method that the Mersenne Twister uses. It cycles through the array instead of shifting all the bits at each step, so that you can have a large state space (hundreds to thousands of bits) with very little computational effort.

Note that since it is a linear method it is not suitable for cryptography.

Answer 3

No, there are no good significantly faster algorithms via general purpose CPUs. As mentioned by @Joachim Isaksson and @Michael Burr, there is not much that can be done without driving down quality or doing something weird e. g: compute at compile time a huge list of random numbers, then run-time generation is fast.

Any real fast random number generator uses specialized hardware. Since you have tagged [microcontroller], check out the processor you are using to see what specialized features it may provide.

Further: providing some more info to your PRN need may help elicit some novel ideas (number length, speed: O(n) or time, degree of randomness, etc.) like using a micro-controller's time based counter modded by a big prime.