<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Seb Francis wrote:
<blockquote TYPE=CITE>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...</blockquote>
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 :-(
<p>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.
<p>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.
<p>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.
<blockquote TYPE=CITE>
<br>I'll post the final algorithm in case it's of use to someone.</blockquote>
Well, here it is for what it's worth ..
<p>This macro generates a random nybble and places it in a register/bits
indicated by input parameters buffer, b0, b1, b2, b3
<p>e.g. To generate a random byte in RND_BUFFER (70 instructions):
<br><tt> GenerateRandom_nybble RND_BUFFER,0,1,2,3</tt>
<br><tt> GenerateRandom_nybble RND_BUFFER,4,5,6,7</tt>
<br>The pattern of bytes will repeat every 131,072 bytes.
<p>e.g. To generate a random 16bit word in RND_BUFFER_L and RND_BUFFER__H
(140 instructions):
<br><tt> GenerateRandom_nybble RND_BUFFER_L,0,1,2,3</tt>
<br><tt> GenerateRandom_nybble RND_BUFFER_L,4,5,6,7</tt>
<br><tt> GenerateRandom_nybble RND_BUFFER_H,0,1,2,3</tt>
<br><tt> GenerateRandom_nybble RND_BUFFER_H,4,5,6,7</tt>
<br>The pattern of words will repeat every 65,536 words (every word is
unique up until this point)
<br>
<p><tt>GenerateRandom_nybble macro buffer, b0, b1, b2,
b3</tt>
<br><tt> clrw</tt><tt></tt>
<p><tt> addlw 1
; RND_SHIFT2,4 -> carry flag</tt>
<br><tt> btfsc RND_SHIFT2,4</tt>
<br><tt> addlw 0xFF</tt>
<br><tt> </tt>
<br><tt> rlf
RND_SHIFT1 ; Rotate RND_SHIFT1 left</tt>
<br><tt> </tt>
<br><tt> bcf
buffer,b0 ; Carry -> buffer,b0</tt>
<br><tt> btfsc STATUS,C</tt>
<br><tt> bsf
buffer,b0</tt>
<br><tt> </tt>
<br><tt> addlw 1
; RND_SHIFT3,3 -> carry flag</tt>
<br><tt> btfsc RND_SHIFT3,3</tt>
<br><tt> addlw 0xFF</tt>
<br><tt> </tt>
<br><tt> rlf
RND_SHIFT2 ; Rotate RND_SHIFT2 left</tt>
<br><tt> </tt>
<br><tt> bcf
buffer,b1 ; Carry -> buffer,b1</tt>
<br><tt> btfsc STATUS,C</tt>
<br><tt> bsf
buffer,b1</tt>
<br><tt> </tt>
<br><tt> addlw 1
; RND_SHIFT4,4 -> carry flag</tt>
<br><tt> btfsc RND_SHIFT4,4</tt>
<br><tt> addlw 0xFF</tt>
<br><tt> </tt>
<br><tt> rlf
RND_SHIFT3 ; Rotate RND_SHIFT3 left</tt>
<br><tt> </tt>
<br><tt> bcf
buffer,b2 ; Carry -> buffer,b2</tt>
<br><tt> btfsc STATUS,C</tt>
<br><tt> bsf
buffer,b2</tt>
<br><tt> </tt>
<br><tt> </tt>
<br><tt> ; !(RND_SHIFT4,4 xor
RND_SHIFT1,4 xor RND_SHIFT3,4) -> carry flag</tt>
<br><tt> </tt>
<br><tt> movf
RND_SHIFT4,w</tt>
<br><tt> xorwf RND_SHIFT1,w</tt>
<br><tt> xorwf RND_SHIFT3,w</tt>
<br><tt> movwf RND_TEMP</tt>
<br><tt> comf
RND_TEMP</tt>
<br><tt> </tt>
<br><tt> clrw</tt>
<br><tt> addlw 1</tt>
<br><tt> btfsc RND_TEMP,4</tt>
<br><tt> addlw 0xFF</tt>
<br><tt> </tt>
<br><tt> </tt>
<br><tt> rlf
RND_SHIFT4 ; Rotate RND_SHIFT4 left</tt>
<br><tt> </tt>
<br><tt> bcf
buffer,b3 ; Carry -> buffer,b3</tt>
<br><tt> btfsc STATUS,C</tt>
<br><tt> bsf
buffer,b3</tt>
<br><tt>endm</tt>
<br><tt></tt> </html>