[sdiy] Pseudo randoms in software

[Magnus Danielson]

From: Seb Francis <seb at is-uk.com>
Subject: [sdiy] Pseudo randoms in software [was: Simplest random source]
Date: Tue, 19 Nov 2002 05:02:48 +0000

> Hi All,

Hi Seb,

> 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! ;)

Well, it is not random enought. I even think it sound very repetitious. It
"looks" random at first thought.

> 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).

If you run the post-processing I talked about, getting the new bits pushed in
from the MSB side, then this is equalent to having an initial RC lowpass filter
with a too high cut-off frequency.

If you *really* want to run the algorithm such that you get 8 or 16 bits out,
there is a parallelized form, which saves you computation as compared to
running the same thing 8 or 16 times over. Well, it should be simpler in
theory, actual CPU cycle count is not necessarilly the same as lower logic-gate
count.

I've done parallelized stuff before, but I'm a little to tired to give you the
details right now.

> 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.

I'm not convinced it get's "better" by running 16 times over. There is
something missing in your argumentation right there.

One should recall that my algorithm takes extra CPU cycles just because I spend
so much time on a long shift register, which adds to the randomness properties
once you've let the initial 1000 or so cycles pass. That takes about 5 ms and
then you see random-ness without looping.

> 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.

Indeed. You *really* want to FFT the waveforms and look at the spectrum. Longer
cycle periods give denser noise, i.e. smaller distances between the integer
multiple of the total cycle time.

> 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 ;)

Well, I'll rather give by bets after looking at some frequency plots, and also
listened in on a few of them.

> 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.

Please do!

Cheers,
Magnus