How to generate random numbers in microcontrollers efficiently?

Question

Any general guidelines? Or particular fast method?

Thanks in advance.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.