Better, faster, random numbers

Many random number generators are software versions of the hardware shift register feedback circuit.   Two problems with this approach are that this operation is usually clumsy in software and the results have some noticeable patterns.

Some time ago, I don't remember just when, I came up with the Chop Suey Machine which works as follows:

Start with a set of memory locations (any size will do).  Add the first value to the second one and store it in the second one.   Now take the result and add it to the third one and store it there.   Continue for as many locations as you like. Finally, add to the 1st byte and swap nibbles.

A three byte implementation in PIC code looks like this....


chop    movf    val1,w     ;get the 1st
        addwf   val2,w     ;add the 2nd
        movwf   val2       ;store the 2nd
        addwf   val3,w     ;add the 3rd & store
        movwf   val3       ;back in 3rd
        addwf   val1       ;add back to 1st
        swapf   val1       ;swap nibbles
        movf    val1,w     ;return one byte
        ret


An initial state of zero's in all locations results in zero's being output.  Seed at least one location with a non zero value to start.   Adding additional locations greatly increases the length of the series while adding very little overhead (2 instructions each).  There is no guarantee of producing a maximum length sequence with this little hack.   You can't even guarantee the sequence length.  Like may random generators, sequence length may depend on the initial values.