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

   1 ! Copyright (C) 2005, 2008 Doug Coleman.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 ! mersenne twister based on
   4 ! http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c
   5 USING: kernel math namespaces sequences sequences.private system
   6 init accessors math.ranges random math.bitwise combinators
   7 specialized-arrays.uint fry ;
   8 IN: random.mersenne-twister
   9
  10 <PRIVATE
  11
  12 TUPLE: mersenne-twister { seq uint-array } { i fixnum } ;
  13
  14 : mt-n 624 ; inline
  15 : mt-m 397 ; inline
  16 : mt-a HEX: 9908b0df ; inline
  17
  18 : mersenne-wrap ( n -- n' )
  19     dup mt-n > [ mt-n - ] when ; inline
  20
  21 : wrap-nth ( n seq -- obj )
  22     [ mersenne-wrap ] dip nth-unsafe ; inline
  23
  24 : set-wrap-nth ( obj n seq -- )
  25     [ mersenne-wrap ] dip set-nth-unsafe ; inline
  26
  27 : calculate-y ( n seq -- y )
  28     [ wrap-nth 31 mask-bit ]
  29     [ [ 1+ ] [ wrap-nth ] bi* 31 bits ] 2bi bitor ; inline
  30
  31 : (mt-generate) ( n seq -- next-mt )
  32     [
  33         calculate-y
  34         [ 2/ ] [ odd? mt-a 0 ? ] bi bitxor
  35     ] [
  36         [ mt-m + ] [ wrap-nth ] bi*
  37     ] 2bi bitxor ; inline
  38
  39 : mt-generate ( mt -- )
  40     [
  41         mt-n swap seq>> '[
  42             _ [ (mt-generate) ] [ set-wrap-nth ] 2bi
  43         ] each
  44     ] [ 0 >>i drop ] bi ; inline
  45
  46 : init-mt-formula ( i seq -- f(seq[i]) )
  47     dupd wrap-nth dup -30 shift bitxor 1812433253 * + 1+ 32 bits ; inline
  48
  49 : init-mt-rest ( seq -- )
  50     mt-n 1- swap '[
  51         _ [ init-mt-formula ] [ [ 1+ ] dip set-wrap-nth ] 2bi
  52     ] each ; inline
  53
  54 : init-mt-seq ( seed -- seq )
  55     32 bits mt-n <uint-array>
  56     [ set-first ] [ init-mt-rest ] [ ] tri ; inline
  57
  58 : mt-temper ( y -- yt )
  59     dup -11 shift bitxor
  60     dup 7 shift HEX: 9d2c5680 bitand bitxor
  61     dup 15 shift HEX: efc60000 bitand bitxor
  62     dup -18 shift bitxor ; inline
  63
  64 : next-index  ( mt -- i )
  65     dup i>> dup mt-n < [ nip ] [ drop mt-generate 0 ] if ; inline
  66
  67 PRIVATE>
  68
  69 : <mersenne-twister> ( seed -- obj )
  70     init-mt-seq 0 mersenne-twister boa
  71     dup mt-generate ;
  72
  73 M: mersenne-twister seed-random ( mt seed -- )
  74     init-mt-seq >>seq drop ;
  75
  76 M: mersenne-twister random-32* ( mt -- r )
  77     [ next-index ]
  78     [ seq>> wrap-nth mt-temper ]
  79     [ [ 1+ ] change-i drop ] tri ;
  80
  81 USE: init
  82
  83 [
  84     [ 32 random-bits ] with-system-random
  85     <mersenne-twister> random-generator set-global
  86 ] "bootstrap.random" add-init-hook