CODEWITHSUNDEEP
algorithmrandom
Jayy
Jayy

Reputation: 14798

Ultra-simple psuedorandom number generation algorithm

I need an algorithm for a microcontroller with extremely limited resources. A 16-bit true random seed will be obtained, after which I need periodic 1-bit random values. The restrictions will be around 4-6 bytes of RAM, and 50 or so bytes of program memory. Instruction cycles are also critical, and the processor does not have multiplication instructions or native floating point capabilities, etc. (It's the PIC16F54). Because of the simple program, it is likely that at times the instruction count between the samples of the random bit are identical. The only saving grace is the degree of randomness is not critical.

Upvotes: 2

Views: 90

Answers (1)

nneonneo
nneonneo

Reputation: 179592

A very quick Google search turns up this 8-bit PRNG which requires just 2 bytes of RAM and has decent randomness properties (see the final post by snigelen).

The code is as follows:

uint8_t rnd(void) {
static uint8_t s=0xaa,a=0;
        s^=s<<3;
        s^=s>>5;
        s^=a++>>2;
        return s;
}

Seed it with a 16-bit quantity by setting s and a with the high and low bytes. You can generate a bit at a time by progressively shifting out the 8-bit result (longer period) or just taking the low bit (faster).

Upvotes: 2

Related Questions