Codebase64 wiki

User Tools

Site Tools

Trace:
base:16bit_xorshift_random_generator

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
base:16bit_xorshift_random_generator [2019-05-10 02:09] – vsariolabase:16bit_xorshift_random_generator [2019-05-10 22:03] – vsariola
Line 4: Line 4:
   * ported by: Veikko Sariola   * ported by: Veikko Sariola
  
-Xorshift is a fast pseudorandom generator algorithm originally developed by [[https://www.jstatsoft.org/article/view/v008i14|George Marsaglia]]. [[http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html|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:+Xorshift is a fast pseudorandom generator algorithm originally developed by [[https://www.jstatsoft.org/article/view/v008i14|George Marsaglia]]. [[http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html|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:
  
 <code c> <code c>
Line 20: Line 20:
 </code> </code>
  
-Here is an implementation for the C64. 25 cycles without the RTS.+Here is an implementation for the C64. 30 cycles without the RTS.
  
 <code asm> <code asm>
Line 31: Line 31:
         STA rng_zp_high         STA rng_zp_high
         ...         ...
-        ; the RNG, you can get 8-bit random numbers in A, leaves X/Y unchanged +        ; the RNG. You can get 8-bit random numbers in A or 16-bit numbers 
-random  LDA rng_zp_low+        ; from the zero page addresses. Leaves X/Y unchanged. 
 +random  LDA rng_zp_high
         LSR         LSR
 +        LDA rng_zp_low
 +        ROR
         EOR rng_zp_high         EOR rng_zp_high
         STA rng_zp_high ; high part of x ^= x << 7 done         STA rng_zp_high ; high part of x ^= x << 7 done
-        ROR             ; A has now x >> 9 and the high bit of the low byte +        ROR             ; A has now x >> 9 and high bit comes from low byte 
-        EOR rng_zp_low  +        EOR rng_zp_low 
-        STA rng_zp_low  ; x ^= x >> 9 done+        STA rng_zp_low  ; x ^= x >> 9 and the low part of x ^= x << 7 done
         EOR rng_zp_high          EOR rng_zp_high 
         STA rng_zp_high ; x ^= x << 8 done         STA rng_zp_high ; x ^= x << 8 done
base/16bit_xorshift_random_generator.txt · Last modified: 2019-08-12 15:41 by ftc