[sdiy] Pseudo randoms in software

[Theo]

How well the counter trick works depends on the ratio between
the "fast" and the slower "event" counter.
Resetting the "event" counter by user action, for example whenever
a key is pressed, can make for some improvement.
And when there is more than one "fast" counter process available,
reading the high and low nibble/byte from different counters also helps.
The more ratios mix the merrier.
Its a cheap method, but the usefulness depends on the application.
I don't expect this to be a good way for generating audio noise.

When the random number is needed on the event of a user action only,
you can just read a fast counter whenever the user action takes place.
No longer "pseudo" random though ;)

Theo


From: Seb Francis <seb at is-uk.com>
To: Magnus Danielson <cfmd at swipnet.se>

> 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&p
ubdate=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
>
>