basis/random/mersenne-twister/mersenne-twister.factor

   1 ! Copyright (C) 2005, 2008 Doug Coleman.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 ! mersenne twister based on
   4 ! https://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c
   5 USING: accessors alien.c-types alien.data fry init kernel math
   6 math.bitwise math.private namespaces random sequences
   7 sequences.private specialized-arrays system ;
   8 SPECIALIZED-ARRAY: uint
   9 IN: random.mersenne-twister
  10
  11 <PRIVATE
  12
  13 TUPLE: mersenne-twister { seq uint-array } { i fixnum } ;
  14
  15 CONSTANT: n 624
  16 CONSTANT: m 397
  17 CONSTANT: a uint-array{ 0 0x9908b0df }
  18
  19 : mt-step ( k+m k+1 k seq -- )
  20     [
  21         [ nth-unsafe ] curry tri@
  22         [ 31 bits ] [ 31 mask-bit ] bi* bitor
  23         [ 2/ ] [ 1 bitand a nth ] bi bitxor bitxor
  24     ] 2keep set-nth-unsafe ; inline
  25
  26 : mt-steps ( k+m k+1 k n seq -- )
  27     [ mt-step ] curry [ 3keep [ 1 + ] tri@ ] curry times 3drop ; inline
  28
  29 : mt-generate ( mt -- )
  30     [
  31         seq>>
  32         [ [ m 1 0 n m - ] dip mt-steps ]
  33         [ [ 0 n m - 1 + n m - m 1 - ] dip mt-steps ]
  34         [ [ m 1 - 0 n 1 - ] dip mt-step ]
  35         tri
  36     ] [ 0 >>i drop ] bi ; inline
  37
  38 : init-mt-formula ( i seq -- f(seq[i]) )
  39     dupd nth dup -30 shift bitxor 1812433253 * + 1 w+ ; inline
  40
  41 : init-mt-rest ( seq -- )
  42     n 1 - swap '[
  43         _ [ init-mt-formula ] [ [ 1 + ] dip set-nth ] 2bi
  44     ] each-integer ; inline
  45
  46 : init-mt-seq ( seed -- seq )
  47     32 bits n uint <c-array>
  48     [ set-first ] [ init-mt-rest ] [ ] tri ; inline
  49
  50 : mt-temper ( y -- yt )
  51     dup -11 shift bitxor
  52     dup 7 shift 0x9d2c5680 bitand bitxor
  53     dup 15 shift 0xefc60000 bitand bitxor
  54     dup -18 shift bitxor ; inline
  55
  56 : next-index  ( mt -- i )
  57     dup i>> dup n < [ nip ] [ drop mt-generate 0 ] if ; inline
  58
  59 PRIVATE>
  60
  61 : <mersenne-twister> ( seed -- obj )
  62     init-mt-seq 0 mersenne-twister boa
  63     dup mt-generate ;
  64
  65 M: mersenne-twister seed-random
  66     init-mt-seq >>seq
  67     dup mt-generate ;
  68
  69 M: mersenne-twister random-32*
  70     [ next-index ]
  71     [ seq>> nth-unsafe mt-temper ]
  72     [ [ 1 fixnum+fast ] change-i drop ] tri ;
  73
  74 : default-mersenne-twister ( -- mersenne-twister )
  75     nano-count <mersenne-twister> ;
  76
  77 STARTUP-HOOK: [
  78     default-mersenne-twister random-generator set-global
  79 ]