[sdiy] Pseudo randoms in software

[Seb Francis]

Hi Magnus,

Magnus Danielson wrote:

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

Good, I can strike this one off my list of options then!  Always nice not to have *too* many possibilities.

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

Remember I'm trying to get a source for a random LFO, not digital noise.

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

I admit I was not beeing fair here just to multiply the CPU cycles of a serial algorithm by 16 - but it gives an idea.

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

It really does - if you just take 16bits out of the shift register on every cycle, then what you have is 1 new bit plus 15 old bits which were one position to the right in the previous number.  This results in many similar repeated features in the random output - see the charts I made.

Ok, so the situation is much improved if you take say 4 (non-adjacent) bits out per cycle (algorithm 5 does this), so it's a little unfair to say you have to run the loop a whole 16 times to get improved randomness.

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

I do agree that it's not fair to compare the CPU cycles your algorithm with that of one with a much smaller shift register.  But remember here that what I'm after is a sequence of random numbers for a random LFO which would typically run much slower than 100Hz and control for example the pitch of a sound.  So a repeat cycle of say 65536 is in fact more than sufficient for most purposes - there seems no need to use such huge shift registers.

BTW, I initialised the shift register in algorithms 3+4 with a random number, not with 0xFF - this kick starts the randomness, rather than having to wait for it to "warm up".

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

This seems valid if I was trying to generate a digital noise source, but what I want is a random LFO - thus the pattern formed by stepping from one value to the next is the interesting thing.  The charts I plotted show 1000 random numbers - this is 10secs @ 100Hz, 100secs @ 10Hz, 1000secs @ 1Hz, so it's a pretty representative chunk.  The visual effect of each algorithm didn't change when plotting randoms further into the sequence - in any case these relatively short shift registers "warm up" very fast.

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

I'll get round to making some mp3s of each random sequence.  This ought to be the best test :)


Thanks as always for your input,
Seb