• original idea: George Marsaglia
• idea for fast 8-bit implementation: John Metcalf
• ported by: Veikko Sariola

Xorshift is a fast pseudorandom generator algorithm originally developed by George Marsaglia. John Metcalf found a 16-bit version of the algorithm that is fast on 8-bit platforms with only single bit shifts available. It has a period of 65535 and passes reasonable tests for randomness. His pseudocode is reprinted here:

/* 16-bit xorshift PRNG */
 
unsigned x = 1;
 
unsigned xorshift( )
{
    x ^= x << 7;
    x ^= x >> 9;
    x ^= x << 8;
    return x;
}

Here is an implementation for the C64. 30 cycles without the RTS.

rng_zp_low = $02
rng_zp_high = $03
        ; seeding
        LDA #1 ; seed, can be anything except 0
        STA rng_zp_low
        LDA #0
        STA rng_zp_high
        ...
        ; the RNG. You can get 8-bit random numbers in A or 16-bit numbers
        ; from the zero page addresses. Leaves X/Y unchanged.
random  LDA rng_zp_high
        LSR
        LDA rng_zp_low
        ROR
        EOR rng_zp_high
        STA rng_zp_high ; high part of x ^= x << 7 done
        ROR             ; A has now x >> 9 and high bit comes from low byte
        EOR rng_zp_low
        STA rng_zp_low  ; x ^= x >> 9 and the low part of x ^= x << 7 done
        EOR rng_zp_high 
        STA rng_zp_high ; x ^= x << 8 done
        RTS

Results: