[sdiy] Simplest random source

[Grant Richter]

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.

From: Seb Francis <seb at is-uk.com>
Organization: IS Innovative Software
Date: Mon, 18 Nov 2002 00:50:28 +0000
To: synth diy <synth-diy at dropmix.xs4all.nl>
Subject: Re: [sdiy] Simplest random source


Seb Francis wrote: 
So I guess it's software after all.  I've been having quite a bit of success
with bitshifts+xors, getting really random 16bit numbers which don't repeat
for 65535 cycles, and using about 50 instructions to generate each number.
This is getting pretty near an acceptable amount of CPU time .. so with a
bit more tweaking...
Well it turned out my estimate of number of instructions (based on the tcl
code) was way off.  In PIC assembler it actually turns out to be 140
instructions to generate a 16 bit random :-(

I've also hunted the web for random algorithms and while there are plenty,
all that I've found seem to be geared towards randomness, rather than speed.

Unfortunatly there just isn't a convenient source for a 16bit random number
in my PIC design.  There are no registers which I can rely on to be a good
random seed.  Timer0 (8bit) will always have the same value when the random
number needs to be generated.  Timer1 (16bit) is only running when a key is
held down.  Time2 (8bit) can be used, but is only 8 bit and probably not so
random because of the timed nature when the LFO needs a new random number.

So I've decided to go for kind of a mixed approach to get 16bits ...
generate an 8bit good quality random number using the bitshift/xor
algorithm. Use this for the MSB, and for the LSB use the MSB xor Timer2
value. Altogether it's about 75 instructions which is _just_ ok to fit in
the available timing slot.
 
I'll post the final algorithm in case it's of use to someone.
Well, here it is for what it's worth ..

This macro generates a random nybble and places it in a register/bits
indicated by input parameters buffer, b0, b1, b2, b3

e.g. To generate a random byte in RND_BUFFER (70 instructions):
 GenerateRandom_nybble RND_BUFFER,0,1,2,3
 GenerateRandom_nybble RND_BUFFER,4,5,6,7
The pattern of bytes will repeat every 131,072 bytes.

e.g. To generate a random 16bit word in RND_BUFFER_L and RND_BUFFER__H (140
instructions): 
 GenerateRandom_nybble RND_BUFFER_L,0,1,2,3
 GenerateRandom_nybble RND_BUFFER_L,4,5,6,7
 GenerateRandom_nybble RND_BUFFER_H,0,1,2,3
 GenerateRandom_nybble RND_BUFFER_H,4,5,6,7
The pattern of words will repeat every 65,536 words (every word is unique up
until this point) 


GenerateRandom_nybble   macro  buffer, b0, b1, b2, b3
        clrw 

        addlw   1              ; RND_SHIFT2,4 -> carry flag
        btfsc   RND_SHIFT2,4
        addlw   0xFF
 
       rlf    RND_SHIFT1      ; Rotate RND_SHIFT1 left
 
       bcf    buffer,b0       ; Carry -> buffer,b0
        btfsc   STATUS,C
        bsf    buffer,b0
 
       addlw   1              ; RND_SHIFT3,3 -> carry flag
        btfsc   RND_SHIFT3,3
        addlw   0xFF
 
       rlf    RND_SHIFT2      ; Rotate RND_SHIFT2 left
 
       bcf    buffer,b1       ; Carry -> buffer,b1
        btfsc   STATUS,C
        bsf    buffer,b1
 
       addlw   1              ; RND_SHIFT4,4 -> carry flag
        btfsc   RND_SHIFT4,4
        addlw   0xFF
 
       rlf    RND_SHIFT3      ; Rotate RND_SHIFT3 left
 
       bcf    buffer,b2       ; Carry -> buffer,b2
        btfsc   STATUS,C
        bsf    buffer,b2
 

       ; !(RND_SHIFT4,4 xor RND_SHIFT1,4 xor RND_SHIFT3,4) -> carry flag
 
       movf   RND_SHIFT4,w
        xorwf   RND_SHIFT1,w
        xorwf   RND_SHIFT3,w
        movwf   RND_TEMP
        comf   RND_TEMP
 
       clrw 
        addlw   1 
        btfsc   RND_TEMP,4
        addlw   0xFF
 

       rlf    RND_SHIFT4      ; Rotate RND_SHIFT4 left
 
       bcf    buffer,b3       ; Carry -> buffer,b3
        btfsc   STATUS,C
        bsf    buffer,b3
endm 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://synth-diy.org/pipermail/synth-diy/attachments/20021117/e04e3a7b/attachment.htm>