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

Next revision		Previous revision
base:16bit_xorshift_random_generator [2019-05-09 23:20] – created 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>
 /* 16-bit xorshift PRNG */ /* 16-bit xorshift PRNG */
  
-unsigned xs = 1;+unsigned x = 1;
  
 unsigned xorshift( ) unsigned xorshift( )
 { {
-    xs ^= xs << 7; +    x ^= x << 7; 
-    xs ^= xs >> 9; +    x ^= x >> 9; 
-    xs ^= xs << 8; +    x ^= x << 8; 
-    return xs;+    return x;
 } }
 </code> </code>
  
-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.+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 ; x ^= x << 7+        ; 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 +        STA rng_zp_high ; high part of x ^= x << 7 done 
-        BCC @skip      ; If the lowest bit was 0, there's no need to EOR +        ROR             ; A has now x >> 9 and high bit comes from low byte
-        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         EOR rng_zp_low
-        STA rng_zp_low +        STA rng_zp_low  ; x ^= x >> 9 and the low part of x ^= x << 7 done 
-        EOR rng_zp_high ; x ^= x << 8 +        EOR rng_zp_high  
-        STA rng_zp_high+        STA rng_zp_high ; x ^= x << 8 done
         RTS         RTS
 </code> </code>
Line 52: Line 51:
  
 {{:base:xorshift_798_results.png?400|}} {{:base:xorshift_798_results.png?400|}}
- 
  
base/16bit_xorshift_random_generator.1557436848.txt.gz · Last modified: 2019-05-09 23:20 by vsariola