Generating pseudo-random (or even fully random) numbers on desktop computers is mostly a solved problem. However, what if we need to generate random numbers on much smaller devices? For example, on Microchip's 8-bit PIC16F1454 microcontroller?

Good news first, mersenne twister is no longer the only player in town. These days we have a whole family of both faster and more random algorithms courtesy of Guy Steele and Sebastiano Vigna. Their xoshiro / xoroshiro generators cover essentially any combination of speed and memory needs. They are probably a pinnacle of randomness quality you can fit in such a minimal space.

Since I did need a minimal footprint, I first selected xoroshiro64**.

Code: xoroshiro64**`uint32_t rotl(const uint32_t x, int k) {`

return (x << k) | (x >> (32 - k));

}

uint32_t s[2];

uint32_t next(void) {

uint32_t s0 = s[0];

uint32_t s1 = s[1];

uint32_t result = rotl(s0 * 0x9E3779BB, 5) * 5;

s1 ^= s0;

s[0] = rotl(s0, 26) ^ s1 ^ (s1 << 9);

s[1] = rotl(s1, 13);

return result;

}

This code will generate random numbers that pass vast majority of DieHarder randomness tests and all that just in `58`

bytes of data memory and `365`

words of program memory (freeware XC8 2.31, with optimizations).

While this is probably as small as a good random number generator can reasonably get on a microcontroller, Microchip PIC is an 8-bit device at heart and dealing with 32-bit values doesn't come naturally. Fortunately, `xoroshiro`

algorithm family scales reasonably well and one can "borrow" the setup.

Here is my stab at making `xoroshiro`

a bit more 8-bit friendly.

Code`uint8_t rotl(const uint8_t x, int k) {`

return (x << k) | (x >> (8 - k));

}

uint8_t s[2] = { 0, 0xA3 };

uint8_t next(void) {

uint8_t s0 = s[0];

uint8_t s1 = s[1];

uint8_t result = s0 + s1;

s1 ^= s0;

s[0] = rotl(s0, 6) ^ s1 ^ (s1 << 1);

s[1] = rotl(s1, 3);

return result;

}

Now, this is a simplified version and definitely not as random as the full implementation. Obvious change is in a state variable size (16 instead of 64) and calculation is taken from `xoroshiro128+`

so that multiplication can be avoided. There are no multiplication circuits in 8-bit PIC microcontrollers and thus this makes code much smaller and faster.

Lastly, the half of initial state is fixed to `0xA3`

. When dealing with such a small state, not all combinations of initial state are valid nor they produce equally long period and this is essentially just a workaround to keep numbers coming.

This simplified version needs `10`

bytes of data memory and takes only `65`

words of program memory. A great improvement (more than 5x in both data and program memory) albeit at significant randomness cost. First of all, you essentially only get `256`

seeds with large enough period (`64897`

bytes). Secondly, the whole space can be only 16-bits to start with. While this might barely pass a few DieHarder tests (e.g. `birthdays`

, `2dsphere`

, `dab_dct`

, and `rgb_permutations`

), it won't come even close to the full `xoroshiro64**`

in terms of randomness quality. And let's not even mention higher state size algorithms.

That said, if you just need random numbers for a game or something similar on a highly constrained device, I would say that quality trade-off is worth the speed and memory usage improvements.

`PS:`

If you initialize random number generator with static values (which is perfectly valid), you will always get the same set of random values. Sometime that is a desired feature (e.g. during debugging) but we usually want something more unpredictable. Assuming you're using the chip with a separate low-frequency oscillator (`LFINTOSC`

), you can rely on a drift between it and a high-frequency oscillator to get a reasonably random seed.

Initialization using LFINTOSC`void init(void) {`

// setup timer if not already in use

T1CONbits.TMR1CS = 0b11;

T1CONbits.T1OSCEN = 1;

T1CONbits.TMR1ON = 1;

_delay(4096); // just to improve randomness of timer - can be omitted

// initialize using timer values (ideally you would wait a bit after starting timer)

s[0] = TMR1L;

s[1] = 0x2A; // important to get high periods and to avoid starting from 0x0000

}

`PPS:`

No, xoshiro algorithms are not cryptographically secure. If you need to generate keys on microcontrollers, look into specialized hardware. These algorithms are intended for general-purpose randomness.

`PPPS:`

Code is available for download. It will use `10`

bytes of data memory and should fit into `82`

words of program memory with initialization from `LFINTOSC`

.