[sdiy] Pseudo randoms in software [was: Simplest random source]

[Seb Francis]

Hi All,

First, some batch-responses ..

Grant Richter wrote:

> Another method is to send a high frequency clock into a counter with rollover. i.e. spin a counter like slot machine wheels. Then use a slow process to sample to counter like freezing the slot machine wheels. If the two clocks are unsynchronized (like a RC oscillator feeding a pin) the difference in speed should produce random results.

This is actually a very nice idea, requiring minimum external components.  With a nice fast external oscillator this should be really quite random.  Just as I thought I was set on an idea .. now more options! ;)


René Schmitz wrote:

> There is no need to run this algorithm 16 times to get to a 16bit value. The
> contents of the shift register change with every iteration. You can use the 2
> lower/higher bytes directly as your random value. If it confuses you that the
> value of the i-th bit is determined by what i-1 was in the iteration before,
> well this whole thing is anything else but random, but purely deterministic.

This is of course true, but I have found that the quality of the random values is much worse if you do this (see below).  In fact to get a proper random 16bit output from Magnus's algorithm you do need to run the loop 16 times (16*19 instructions).


Scott Gravenhorst wrote:

> http://home1.gte.net/res0658s/xapp052.pdf
>
> A Xylinx PDF detailing much of this.  On page 5 you will see a chart that has feedback points for
> shift registers up to 168 bits.

Very useful, thanks!



phillip m gallo (or was it Paul Perry) wrote:

> You might be interest in the following:
>
> http://www.e-insite.net/ednmag/index.asp?layout=article&articleId=CA200385&pubdate=03/21/2002
>

This is a neat little algorithm, and it produces really quite random looking output, with only 10 instructions per loop!  Again though, the same principle applies as with Magnus's algorithm - to get good quality output you need to run the loop n times where n is the number of bits you want .. so for 16bits that's 160 instructions, plus a few more to actually get out the number, and save the carry flag somewhere between calls.


Since there seem to be many similar (but not identical) methods of generating pseudo randoms I decided to investigate further.  What I'm actually after is something which will *sound* (pleasingly) random - the human brain recognises patterns in subtle ways.

Since it takes too long to listen to lots of different random sequences and it's hard to compare them side by side, I decided to plot some graphs of the different algorithms to get a feel for the randomness.  I hope this also gives some feeling of the "pleasantness" of each stream of random numbers - I know this is not very mathematical, but hey I'm a musician not a mathematician ;)

The results are here:
http://burnit.co.uk/random.html

The 5th chart is the algorithm I originally posted - and from a visual (which hopefully = aural) point of view it is my favourite. .. you can make up you own minds.  I need to get it to run a bit faster .. I'm fairly sure it can be optimised somewhat.  I'll re-post it if I have any success.


cu,
Seb