Codebase64 wiki

• 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, unlike most of the LFSRs on this site. His pseudocode is reprinted here:

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

Here is an implementation for the C64. 38 cycles if branch not taken (without the RTS), 31 if branch is taken, which should be about half of the time, so on average 34.5 cycles.

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, leaves X/Y unchanged
random  LDA rng_zp_low ; x ^= x << 7
        LSR
        EOR rng_zp_high
        STA rng_zp_high
        BCC @skip      ; If the lowest bit was 0, there's no need to EOR
        LDA #%10000000 ; the highest bit of the low byte.
        EOR rng_zp_low ; Carry was set, EOR highest bit.
        STA rng_zp_low
@skip   LDA rng_zp_high ; x ^= x >> 9
        LSR
        EOR rng_zp_low
        STA rng_zp_low
        EOR rng_zp_high ; x ^= x << 8
        STA rng_zp_high
        RTS

Results: