EternityForest.Com

JavaScript is disabled or not working. Turn On JavaScript and get awesome text here with every click.



Projects:

Simple 8-Bit PseudoRandom-Number Generators:

Introduction:

Many Times in computing there is a need for a simple source of random numbers, or numbers appearing to be random at the very least.
(A deterministic process cannot produce true randomness, for that you need a hardware device looking at quantum phenomena like noise in an analog circuit, which are not difficult to build)
There are many algorithms available to create such numbers, each with its own strengths and weaknesses.
In this page I will present my own XABC and XABC-1 algorithms, a modified version of XORShift, and talk a little on the available alternatives.

What is out there now?

RC4

My favorite algorithm of all time for this sort of thing has to be ARC4. designed by Ron Rivest in the 80's i believe, this algorithm was intended for use as a cryptographic cipher.
This use has come under much scrutiny, and some people do not believe that it is secure enough. Regardless of its use in High-Security environments, it is a great fast algorithm for general use. The only disadvantages are it requires 256 bytes of ram for the internal state, and needs several array accesses to get each byte. But, it is extremely fast, even on embedded systems, and creates very good quality numbers. The algorithm is simple, consisting of:

i++;
j = j + s[i];
swap s[i] and s[j];
k = s[s[i]+s[j]];
output k;

Where s is a permutation of 0,255
And all values are 8 bit,.

LCG

Another algorithm in common use is the Linear Congruential Generator. LCGs are reasonably fast, and depending on the parameters can create reasonable numbers.
the low order bits are less random then the high order ones, and it requires an addition, a multiplication, and a modulo to generate a few bytes. Not very fast on an 8 bit with no hardware multiply. This algorithm is also known as AX+B mod P , which pretty much describes its entire operation.

Mersenne Twister

The Mersenne Twister is another popular algorithm, commonly used in games and scientific simulations. it is very fast and produces very good quality numbers, but requires 2k of ram or so.

LFSR/XORSHIFT

The Linear Feedback Shift Register and its close relative , XORSHIFT, produce decent output in only a few bytes of ram. The output is not perfect, however, and they often require up to 8 left or right shift operations alone on device with no barrel shifter. Nevertheless, they are one of the fastest options.

XABC and XABC-2:

XABC is a simple algorithm requiring only seven operations per byte, with no multiplications or divides or other slow operations.
It uses 4 bytes of ram and has a period of 450 million or so for most seeds. There might be a weak seed somewhere with a pediod of 5, but in some applications it might still be useful. Maybe play around and mix in a hardware timer value somewhere to add some entropy and make short cycles less likely. It's probably not an issue of you are generating white noise or led flickering.

If you don't need the speed and want higher quality, consider using a proper RNG with a full period. XORshift is probably fast enough for most​ things except maybe audio on slow chips.
That said this algorithm sometimes comes in handy when working with really small chips, and the period is probably not going to be short enough that anyone will notice in a lot of applications.

The algorithm:

x++;
a = (a^c^x);
b = (b+a);
c = (c+(b>>1)^a);
return(c);


XABC in its basic state fails most of the Overlapping Sparse Occupancy tests according to DIEHARD. It also does not have full period for 32 bits like a LFSR does.
It is, however, a lot faster then an LFSR or LCG


XABC-2 is a very similar algorithm, except that the left shift of b has been replaced with a AES S-Box substitution step. This allows it to create very good quality output at the expense of 256 bytes of flash(not ram, the table is fixed) to store the permutation table. The permutation table is the same as AES, based on some complicated math that I don't understand which makes sure it mixes everything up well. Read up on AES for the full story. XABC-2 does not fail any DIEHARD tests.
           

The improved algorithm:

x++;
a = (a^c^x);
b = (b+a);
c = (c+(inv_s[b])^a);
    return(c);

As you can see, XABC-2 is very similar to XABC-1. Both will probably be good enough for most things, But the second is much better according to the DIEHARD test suite.
I have included a C language library here, which you can use simply by including it, optionally calling init_rng(s1,s2,s3) and providing a three byte seed value(you can set any of them to zero if you have only one or to bytes of seed entropy) and then calling randomize() to get a 8 bit unsigned char of random data.

You will most likely want to periodically call init_rng to avoid your device or application producing repetitive sequences.
Good sources of entropy for this purpose include MCU built in temperature sensors, floating ADC pins, timer values when the user presses a button,etc.
On the other hand, you may want the same sequence every time, in that case just seed once at startup and leave it alone after.


Modified XORshift for Arduino(My new favorite):

George Marsaglia invented a really cool RNG called XORshift. There is a ton of versions possible from 8 bits to 128 bits and more. It's not statistically perfect but it's fast and has a full period for it's size.

What I like to is combine it with the micros() function on the arduino. Micros can be pretty random if you have an inputs. I find that the result often 100% passes dieharder, which is very impressive for it's size. Here is th code I use:

uint32_t y;

//When you call this, y will be set to a random value that depends on both it's previous value,
//And the exact time you called it, and by extension the exact time of every previous call.
void rng()
{
    y+=micros();
    y^=y<<2;y^=y>>7;y^=y<<7;
}

The results are much better than XABC, but it will likely be less than half as fast. Performance is still much better than Arduino's random() function.

I hope this algorithm and library is useful to somebody. But no warranty of any sort is given,
and I strongly recommend against using it for cryptography or important scientific calculations.

This algorithm is good enough for toys, games, audio, and what not,
but use it at your own risk for anything important