here with every click.
Simple 8-Bit PseudoRandom-Number Generators:
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?
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:
j = j + s[i];
swap s[i] and s[j];
k = s[s[i]+s[j]];
Where s is a permutation of 0,255
And all values are 8 bit,.
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.
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.
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.
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);
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):
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:
//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.
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