[Fwd: Re: [sdiy] Simplest random source]

[Seb Francis]

Magnus Danielson wrote:

> Hi Seb,
>
> You where breaking up in a lot of HTML noise, could you repeat that in plain
> ASCII/ISO Latin 1?
>
> Cheers,
> Magnus

Should be better ..

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

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