User Tools

Site Tools


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
base:16bit_xorshift_random_generator [2019-05-10 02:09] vsariolabase:16bit_xorshift_random_generator [2019-08-12 15:41] (current) – Standardized format of the heading ftc
Line 1: Line 1:
-=== 16-bit "798" Xorshift ===+====== 16-bit "798" Xorshift ====== 
   * original idea: [[https://www.jstatsoft.org/article/view/v008i14|George Marsaglia]]   * original idea: [[https://www.jstatsoft.org/article/view/v008i14|George Marsaglia]]
   * idea for fast 8-bit implementation: [[http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html|John Metcalf]]   * idea for fast 8-bit implementation: [[http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html|John Metcalf]]
   * 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 21:
 </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 32:
         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
Line 47: Line 51:
  
 {{:base:xorshift_798_results.png?400|}} {{:base:xorshift_798_results.png?400|}}
- 
  
base/16bit_xorshift_random_generator.1557446995.txt.gz · Last modified: 2019-05-10 02:09 by vsariola