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

[Seb Francis]

Do I understand right that this code only produces 1 random bit per cycle, so to get a 16bit random number you have to loop 16 times (16*19 instructions)?

Maybe it's a bit late at night and I'm not understanding it properly..

Thanks,
Seb


Magnus Danielson wrote:

> From: Seb Francis <seb at is-uk.com>
> Subject: [Fwd: Re: [sdiy] Simplest random source]
> Date: Mon, 18 Nov 2002 01:52:45 +0000
>
> > 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 :-(
>
> That sounds like a little too much. You should be down to a handfull
> instructions. Allready 50 sounded too much, but I'm not PIC assembler fluent
> person.
>
> Let's see... a 64 bit shift register core ought to be something like this
>
> LSHIFT:
>         RLF     SHIFT0
>         RLF     SHIFT1
>         RLF     SHIFT2
>         RLF     SHIFT3
>         RLF     SHIFT4
>         RLF     SHIFT5
>         RLF     SHIFT6
>         RLF     SHIFT7
>
> where the carry bit is both input and output.
>
> To generate the input carry bit for X^63+X+1 we need to do:
> TERMGEN:
>         MOVF    SHIFT7,w
>         MOVWF   TERM
>         RLF     TERM
>         RLF     TERM
>         MOVF    SHIFT0,w
>         XORWF   TERM
>         RRF     TERM
>
> The output term naturally has to be formulated, and here I toss the output to
> pin RB0 (dirty, TERM is wasted here):
>
> OUTPIN:
>         RLF     TERM
>         MOVWF   6
>
> We need to initialized this one, which we do by writing 1's into the shift
> register:
>
> INIT:
>         MOVLW   0xff
>         MOVWF   SHIFT0
>         MOVWF   SHIFT1
>         MOVWF   SHIFT2
>         MOVWF   SHIFT3
>         MOVWF   SHIFT4
>         MOVWF   SHIFT5
>         MOVWF   SHIFT6
>         MOVWF   SHIFT7
>
> So, this would give the following structure:
>
> INIT:
>         MOVLW   0xff
>         MOVWF   SHIFT0
>         MOVWF   SHIFT1
>         MOVWF   SHIFT2
>         MOVWF   SHIFT3
>         MOVWF   SHIFT4
>         MOVWF   SHIFT5
>         MOVWF   SHIFT6
>         MOVWF   SHIFT7
> TERMGEN:
>         MOVF    SHIFT7,w
>         MOVWF   TERM
>         RLF     TERM
>         RLF     TERM
>         MOVF    SHIFT0,w
>         XORWF   TERM
>         RRF     TERM
> LSHIFT:
>         RLF     SHIFT0
>         RLF     SHIFT1
>         RLF     SHIFT2
>         RLF     SHIFT3
>         RLF     SHIFT4
>         RLF     SHIFT5
>         RLF     SHIFT6
>         RLF     SHIFT7
> OUTPIN:
>         RLF     TERM
>         MOVWF   6
>         GOTO    TERMGEN
>
> Which is a mere 27 instruction (28 bytes) variant for a 63 bit long shift
> register. The loop will keep the speed of 18 CPU cycles, and there is no point
> in keeping it down to a slower speed, since this thing is looooong enought so
> looping is not an issue.
>
> I have not test-run this thing yeat, but I could do that. PIC gurus could
> probably point out all the misstakes I've done. Naturally, there is means to
> optimize this, like treating the shift registers as a rotating buffer. Question
> is if the processing needed bumps of any cycles or not. Anyway, this code is
> small enougth to fit into most PICs. It has a small memory footprint (28 byte
> code and 9 bytes of register memory, weighing in at 37 bytes) so that should
> not be an issue.
>
> Oh, I've looked at the PIC16C71, so you might have to mangle the code and
> result slightly to perfectly fit the PIC of your choice.
>
> > 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.
>
> I've hoped I've given you an indication of what you could acheive speedwise.
>
> > 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.
>
> You don't have much use of a random seed when you run such an algorihtm in
> continous mode. You will soon not notice where you started anyway.
>
> > 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.
>
> Wasted effort IMHO. If you go for a deep polynom like I have, you've lost track
> of things since you started, and it keeps ticking "in random" without looping
> on you.
>
> Cheers,
> Magnus - Am I a PIC hacker now???