<HTML>
<HEAD>
<TITLE>Re: [sdiy] Simplest random source</TITLE>
</HEAD>
<BODY>
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.<BR>
<BLOCKQUOTE><BR>
<B>From: </B>Seb Francis <seb@is-uk.com><BR>
<B>Organization: </B>IS Innovative Software<BR>
<B>Date: </B>Mon, 18 Nov 2002 00:50:28 +0000<BR>
<B>To: </B>synth diy <synth-diy@dropmix.xs4all.nl><BR>
<B>Subject: </B>Re: [sdiy] Simplest random source<BR>
<BR>
</BLOCKQUOTE><BR>
<BLOCKQUOTE>Seb Francis wrote: <BR>
<BLOCKQUOTE>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...<BR>
</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 :-( <BR>
<BR>
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. <BR>
<BR>
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. <BR>
<BR>
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. <BR>
<BLOCKQUOTE> <BR>
I'll post the final algorithm in case it's of use to someone.<BR>
</BLOCKQUOTE>Well, here it is for what it's worth .. <BR>
<BR>
This macro generates a random nybble and places it in a register/bits indicated by input parameters buffer, b0, b1, b2, b3 <BR>
<BR>
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. <BR>
<BR>
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>
<BR>
<BR>
<TT>GenerateRandom_nybble macro buffer, b0, b1, b2, b3</TT> <BR>
<TT> clrw</TT> <BR>
<BR>
<TT> addlw 1 ; RND_SHIFT2,4 -> carry flag</TT> <BR>
<TT> btfsc RND_SHIFT2,4</TT> <BR>
<TT> addlw 0xFF</TT> <BR>
<TT> <BR>
rlf RND_SHIFT1 ; Rotate RND_SHIFT1 left</TT> <BR>
<TT> <BR>
bcf buffer,b0 ; Carry -> buffer,b0</TT> <BR>
<TT> btfsc STATUS,C</TT> <BR>
<TT> bsf buffer,b0</TT> <BR>
<TT> <BR>
addlw 1 ; RND_SHIFT3,3 -> carry flag</TT> <BR>
<TT> btfsc RND_SHIFT3,3</TT> <BR>
<TT> addlw 0xFF</TT> <BR>
<TT> <BR>
rlf RND_SHIFT2 ; Rotate RND_SHIFT2 left</TT> <BR>
<TT> <BR>
bcf buffer,b1 ; Carry -> buffer,b1</TT> <BR>
<TT> btfsc STATUS,C</TT> <BR>
<TT> bsf buffer,b1</TT> <BR>
<TT> <BR>
addlw 1 ; RND_SHIFT4,4 -> carry flag</TT> <BR>
<TT> btfsc RND_SHIFT4,4</TT> <BR>
<TT> addlw 0xFF</TT> <BR>
<TT> <BR>
rlf RND_SHIFT3 ; Rotate RND_SHIFT3 left</TT> <BR>
<TT> <BR>
bcf buffer,b2 ; Carry -> buffer,b2</TT> <BR>
<TT> btfsc STATUS,C</TT> <BR>
<TT> bsf buffer,b2</TT> <BR>
<TT> <BR>
<BR>
; !(RND_SHIFT4,4 xor RND_SHIFT1,4 xor RND_SHIFT3,4) -> carry flag</TT> <BR>
<TT> <BR>
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> <BR>
clrw</TT> <BR>
<TT> addlw 1</TT> <BR>
<TT> btfsc RND_TEMP,4</TT> <BR>
<TT> addlw 0xFF</TT> <BR>
<TT> <BR>
<BR>
rlf RND_SHIFT4 ; Rotate RND_SHIFT4 left</TT> <BR>
<TT> <BR>
bcf buffer,b3 ; Carry -> buffer,b3</TT> <BR>
<TT> btfsc STATUS,C</TT> <BR>
<TT> bsf buffer,b3</TT> <BR>
<TT>endm</TT> <BR>
<BR>
</BLOCKQUOTE><BR>
</BODY>
</HTML>