How can I get random numbers on AVR?

Question

I am trying to make the game MegaMind. I need to get a random number, but how can I get them on AVR?

I have tried this:

secret_code[1] = random()&=6;

Answer 1

Random Numbers and Computers

Let us talk a second about what it takes to generate random numbers.

Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.

That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.

In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).

But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.

Pseudo-random number generation on microcontrollers in practice

On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.

Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.

For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.

Seeding your PRNG

The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!

That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.

But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.

Answer 2

From the AVR Libc Reference Manual, under stdlib.h: General utilities:

Function rand():

int rand(void)

The rand() function computes a sequence of pseudo-random integers in the range of 0 to RAND_MAX (as defined by the header file <stdlib.h>).

The srand() function sets its argument seed as the seed for a new sequence of pseudo-random numbers to be returned by rand(). These sequences are repeatable by calling srand() with the same seed value.

If no seed value is provided, the functions are automatically seeded with a value of 1.

In compliance with the C standard, these functions operate on int arguments. Since the underlying algorithm already uses 32-bit calculations, this causes a loss of precision. See random() for an alternate set of functions that retains full 32-bit precision.

Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.

A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.

Answer 3

The other answers are more theoretical, but I have done some practical experiments in this area.

Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.

This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c

I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.

For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.

Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.

Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because its frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.

Answer 4

Count the time in ms from the time the device was first turned on and the first user interaction, mod (%) that count by some number, say 99 and then use that number to seed the random number generator (srand()). At least that's what I would do.

Answer 5

https://www.codeproject.com/Articles/5311070/A-True-Random-Number-Generator-in-Arduino-AVR-ATme

Here is a simple trick to get a REAL random number in ATmega328 (it applies to most ATmega controllers that have an option to attach the ADC mux to internal 1.1/VC.) I'm not sure whether to call the number truly random because it is generated from the physics of the hardware and can still have sort of patterns that arise from the oscillations of the hardware, maybe.

The trick is to abuse the ADC by generating a pulsating signal on the input that can never be truly pulsating because the lines have got to have some capacitance.

int N = 20; // 20 works really fine for uint8, can be increased to reduce patterns. Each cicle takes around 80us on 16Mhz main clock which give a random nmumber almost every 1.5ms.
for (int i = 0; i < N; i++)
{
  if (i % 2 == 0)
    ADMUX = 0b01001110; // High (1.1V)
  else
    ADMUX = 0b01001111; // Low (0V)
  ADCSRA |= 1 << ADSC; // Start a conversion
  uint8_t low, high;
  // ADSC is cleared when the conversion finishes
  while ((ADCSRA >> ADSC) % 2); // wait for the conversion to complete
  low  = ADCL; // do not swap this sequence. Low has to be fetched first.
  high = ADCH; // the value is always between 0-3
  V ^= low; 
  V ^= high;

  // Lets shift rotate the number;

  uint8_t last = V % 2;
  V >>= 1;
  V |= last << 7;
  // Disable the ADC
  ADCSRA = 0;
  // Enable the ADC with a randomly selected clock Prescaler between 2 and 128. since each conversion takes 13 ADC cycles, at 16Mhz system clock, the ADC will now take something in between 1.6us and 104us for each conversion.
  ADCSRA = 0b10000000 | ((V % 4) << 1);
}