How do I generate random numbers in a microcontroller efficiently?

How do I generate random numb开发者_开发百科ers in a microcontroller efficiently? Are there any general guidelines or a particular fast method?

One normally generates pseudo-random numbers and not actual random numbers, although both are possible at varying rates.

There are two general categories, depending on whether the sequence will be used for cryptographic purposes. The primary distinction is whether knowledge of one number in the sequence allows prediction of the next. General purpose RNG's don't worry about whether knowledge of the algorithm would allow an observer to duplicate the sequence, and they run quite a bit faster.

A typical general purpose RNG algorithm is the Mersenne Twister. There are many public implementations of various algorithms. See here for one.

If the MT requires too much memory, a half-way-decent fallback is the linear congruential generator. (The MT wasn't invented until 1997.) This generator has certain issues but it requires almost no memory, almost no code, and is extremely fast. Implementations are everywhere, and it was covered in detail in Knuth's Seminumerical Algorithms.

To seed any RNG, you will need a source of entropy, see http://en.wikipedia.org/wiki/Entropy_(computing) (Note: SO gets confused about the ()'s in that link.) This is typically derived by timing events that the CPU can observe, such as keystrokes, (I guess that won't work for you) interrupts, and packet arrivals. A real time clock is often an acceptable source if it maintains its own state, as reboots are rarely timed in any sort of sequence.

you can store a seed to EEPROM, and when device boots, you can increment a seed and store it again. So, every reboot youll have different random number.

You can generate pseudorandom numbers by manipulation of bits by simulating a LINEAR FEEDBACK SHIFT REGISTER

The question then becomes 'how many bits do you want to simulate?'

Wikipedia has some information.

If you have access to an ADC, then you can read the least significant bit from it, and use it as a seed for a Pseudo Random Number Generator, like others have posted. Obviously you will need to read more than one bit from the ADC, so multiple reads are needed, which could take a while. But you only need to do this once, at startup for example, and then use faster PRNG to generate new random numbers.

Many embeded devices have built inn ADC, for example the ATMega family form Atmel.

If the hardware has a button for the user, a simple trick is to count how long the button is pressed. With a fast enough short counter you get a "random" number.

Pseudo random number generators that are the fastest and least demanding w.r.t. the instruction set (only shift and xor, no multiplication or division) are smaller variants of the Mersenne twister idea (called Generalized Linear Feedback Shift register). Mersenne twister itself needs too much memory for microcontrollers.

The problem with these generators is that they may generate long sequences near zero if you are unlucky. With a reasonable size of the state space and initialization from another PNRG this is however unlikely.

They are also not secure for cryptography or gambling, an intelligent adversary can predict future states after observing the output. This is because they are linear.

I once designed such a generator for a small nonstandard processor with a state space of about 50 24-bit words. I tested variants with the Diehard test suite until I found a good one. The application was generating random variations for a hardware test.

Reading the timer and xoring/nanding/etc it with a series of bits will give a semi random to the user, as the timing between events is likely to be enough apart that the user won't really be able to tell the correlation with the timer.

If you can leave a pin floating, it could help to generate random numbers with linear feedback shift register. I'm not sure this is the way to go, but please have a look at my code:

// This code was written for 8051 (AT89S52)
unsigned char lfsr = 231; //8 bit shift register, with the seed of 231 or '11100111b'
unsigned char input_bit, i;

void main (void) 
{
    //Setup
    P0_0 = 0; // Leave Pin 0 Port 0 floating
    uart_init(); //Initializing uart/serial communication with pc


    while (1) 
    {
        for (i = 0; i < 255; i++) 
        {
            if (P0_0 == 1) // If Pin 0.0 is HIGH
            {
                input_bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1;
                lfsr = (lfsr >> 1) | (input_bit << 7);
            }
        }
        printf_tiny("%u\n", lfsr); //Send the random number to PC
        soft_delay(65535); //Simple delay function
    } //end while (1) loop

}

EDIT: I found out my answer may be a bad one. More details on why should not use a floating digital pin: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin