basis/random/random.factor

   1 ! Copyright (C) 2008 Doug Coleman.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors alien.c-types alien.data arrays assocs
   4 byte-arrays byte-vectors combinators combinators.short-circuit
   5 fry io.backend io.binary kernel locals math math.bitwise
   6 math.constants math.functions math.order math.ranges namespaces
   7 sequences sequences.private sets summary system vocabs hints
   8 typed ;
   9 IN: random
  10
  11 SYMBOL: system-random-generator
  12 SYMBOL: secure-random-generator
  13 SYMBOL: random-generator
  14
  15 GENERIC# seed-random 1 ( tuple seed -- tuple' )
  16 GENERIC: random-32* ( tuple -- r )
  17 GENERIC: random-bytes* ( n tuple -- byte-array )
  18
  19 M: object random-bytes* ( n tuple -- byte-array )
  20     [ [ <byte-vector> ] keep 4 /mod ] dip
  21     [ pick '[ _ random-32* int <ref> _ push-all ] times ]
  22     [
  23         over zero?
  24         [ 2drop ] [ random-32* int <ref> swap head append! ] if
  25     ] bi-curry bi* B{ } like ;
  26
  27 HINTS: M\ object random-bytes* { fixnum object } ;
  28
  29 M: object random-32* ( tuple -- r ) 4 swap random-bytes* be> ;
  30
  31 ERROR: no-random-number-generator ;
  32
  33 M: no-random-number-generator summary
  34     drop "Random number generator is not defined." ;
  35
  36 M: f random-bytes* ( n obj -- * ) no-random-number-generator ;
  37
  38 M: f random-32* ( obj -- * ) no-random-number-generator ;
  39
  40 : random-32 ( -- n ) random-generator get random-32* ;
  41
  42 TYPED: random-bytes ( n: fixnum -- byte-array: byte-array )
  43     random-generator get random-bytes* ; inline
  44
  45 <PRIVATE
  46
  47 : (random-integer) ( bits -- n required-bits )
  48     [ random-32 32 ] dip 32 - [ dup 0 > ] [
  49         [ 32 shift random-32 + ] [ 32 + ] [ 32 - ] tri*
  50     ] while drop ;
  51
  52 : random-integer ( n -- n' )
  53     dup next-power-of-2 log2 (random-integer)
  54     [ * ] [ 2^ /i ] bi* ;
  55
  56 PRIVATE>
  57
  58 : random-bits ( numbits -- r ) 2^ random-integer ;
  59
  60 : random-bits* ( numbits -- n )
  61     1 - [ random-bits ] keep set-bit ;
  62
  63 GENERIC: random ( obj -- elt )
  64
  65 M: integer random [ f ] [ random-integer ] if-zero ;
  66
  67 M: sequence random
  68     [ f ] [
  69         [ length random-integer ] keep nth
  70     ] if-empty ;
  71
  72 : randomize-n-last ( seq n -- seq )
  73     [ dup length dup ] dip - 1 max '[ dup _ > ]
  74     [ [ random ] [ 1 - ] bi [ pick exchange-unsafe ] keep ]
  75     while drop ;
  76
  77 : randomize ( seq -- randomized )
  78     dup length randomize-n-last ;
  79
  80 ERROR: too-many-samples seq n ;
  81
  82 : sample ( seq n -- seq' )
  83     2dup [ length ] dip < [ too-many-samples ] when
  84     [ [ length iota >array ] dip [ randomize-n-last ] keep tail-slice* ]
  85     [ drop ] 2bi nths ;
  86
  87 : delete-random ( seq -- elt )
  88     [ length random-integer ] keep [ nth ] 2keep remove-nth! drop ;
  89
  90 : with-random ( tuple quot -- )
  91     random-generator swap with-variable ; inline
  92
  93 : with-system-random ( quot -- )
  94     system-random-generator get swap with-random ; inline
  95
  96 : with-secure-random ( quot -- )
  97     secure-random-generator get swap with-random ; inline
  98
  99 : uniform-random-float ( min max -- n )
 100     4 random-bytes uint deref >float
 101     4 random-bytes uint deref >float
 102     2.0 32 ^ * +
 103     [ over - 2.0 -64 ^ * ] dip
 104     * + ; inline
 105
 106 : random-unit ( -- n )
 107     0.0 1.0 uniform-random-float ; inline
 108
 109 : random-units ( length -- sequence )
 110     [ random-unit ] replicate ;
 111
 112 : random-integers ( length n -- sequence )
 113     '[ _ random ] replicate ;
 114
 115 : (cos-random-float) ( -- n )
 116     0. 2pi uniform-random-float cos ;
 117
 118 : (log-sqrt-random-float) ( -- n )
 119     random-unit log -2. * sqrt ;
 120
 121 : normal-random-float ( mean sigma -- n )
 122     (cos-random-float) (log-sqrt-random-float) * * + ;
 123
 124 : lognormal-random-float ( mean sigma -- n )
 125     normal-random-float e^ ;
 126
 127 : exponential-random-float ( lambda -- n )
 128     random-unit log neg swap / ;
 129
 130 : weibull-random-float ( alpha beta -- n )
 131     [
 132         [ random-unit log neg ] dip
 133         1. swap / ^
 134     ] dip * ;
 135
 136 : pareto-random-float ( k alpha -- n )
 137     [ random-unit ] dip recip ^ /f ;
 138
 139 :: (gamma-random-float>1) ( alpha beta -- n )
 140     ! Uses R.C.H. Cheng, "The generation of Gamma
 141     ! variables with non-integral shape parameters",
 142     ! Applied Statistics, (1977), 26, No. 1, p71-74
 143     2. alpha * 1 - sqrt :> ainv
 144     alpha 4. log -      :> bbb
 145     alpha ainv +        :> ccc
 146
 147     0 :> r! 0 :> z! 0 :> result! ! initialize locals
 148     [
 149         r {
 150             [ 1. 4.5 log + + z 4.5 * - 0 >= ]
 151             [ z log >= ]
 152         } 1|| not
 153     ] [
 154         random-unit :> u1
 155         random-unit :> u2
 156
 157         u1 1. u1 - / log ainv / :> v
 158         alpha v e^ *           :> x
 159         u1 sq u2 *              z!
 160         bbb ccc v * + x -       r!
 161
 162         x beta *                result!
 163     ] do while result ;
 164
 165 : (gamma-random-float=1) ( alpha beta -- n )
 166     nip random-unit log neg * ;
 167
 168 :: (gamma-random-float<1) ( alpha beta -- n )
 169     ! Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
 170     alpha e + e / :> b
 171
 172     0 :> x! 0 :> p! ! initialize locals
 173     [
 174         p 1.0 > [
 175             random-unit x alpha 1 - ^ >
 176         ] [
 177             random-unit x neg e^ >
 178         ] if
 179     ] [
 180         random-unit b * p!
 181         p 1.0 <= [
 182             p 1. alpha / ^
 183         ] [
 184             b p - alpha / log neg
 185         ] if x!
 186     ] do while x beta * ;
 187
 188 : gamma-random-float ( alpha beta -- n )
 189     {
 190         { [ over 1 > ] [ (gamma-random-float>1) ] }
 191         { [ over 1 = ] [ (gamma-random-float=1) ] }
 192         [ (gamma-random-float<1) ]
 193     } cond ;
 194
 195 : beta-random-float ( alpha beta -- n )
 196     [ 1. gamma-random-float ] dip over zero?
 197     [ 2drop 0 ] [ 1. gamma-random-float dupd + / ] if ;
 198
 199 :: von-mises-random-float ( mu kappa -- n )
 200     ! Based upon an algorithm published in: Fisher, N.I.,
 201     ! "Statistical Analysis of Circular Data", Cambridge
 202     ! University Press, 1993.
 203     kappa 1e-6 <= [
 204         2pi random-unit *
 205     ] [
 206         4. kappa sq * 1. + sqrt 1. + :> a
 207         a 2. a * sqrt - 2. kappa * / :> b
 208         b sq 1. + 2. b * /           :> r
 209
 210         0 :> c! 0 :> _f! ! initialize locals
 211         [
 212             random-unit {
 213                 [ 2. c - c * < ] [ 1. c - e^ c * <= ]
 214             } 1|| not
 215         ] [
 216             random-unit pi * cos :> z
 217             r z * 1. + r z + /   _f!
 218             r _f - kappa *       c!
 219         ] do while
 220
 221         mu 2pi mod _f cos random-unit 0.5 > [ + ] [ - ] if
 222     ] if ;
 223
 224 :: (triangular-random-float) ( low high mode -- n )
 225     mode low - high low - / :> c!
 226     random-unit :> u!
 227     high low
 228     u c > [ 1. u - u! 1. c - c! swap ] when
 229     [ - u c * sqrt * ] keep + ;
 230
 231 : triangular-random-float ( low high -- n )
 232     2dup + 2 /f (triangular-random-float) ;
 233
 234 : laplace-random-float ( mean scale -- n )
 235     random-unit dup 0.5 <
 236     [ 2 * log ] [ 1 swap - 2 * log neg ] if * + ;
 237
 238 : cauchy-random-float ( median scale -- n )
 239     random-unit 0.5 - pi * tan * + ;
 240
 241 : chi-square-random-float ( dof -- n )
 242     [ 0.5 ] dip 2 * gamma-random-float ;
 243
 244 : student-t-random-float ( dof -- n )
 245     [ 0 1 normal-random-float ] dip
 246     [ chi-square-random-float ] [ / ] bi sqrt / ;
 247
 248 : inv-gamma-random-float ( shape scale -- n )
 249     recip gamma-random-float recip ;
 250
 251 : rayleigh-random-float ( mode -- n )
 252     random-unit log -2 * sqrt * ;
 253
 254 : gumbel-random-float ( loc scale -- n )
 255     random-unit log neg log * - ;
 256
 257 : logistic-random-float ( loc scale -- n )
 258     random-unit dup 1 swap - / log * + ;
 259
 260 : power-random-float ( alpha -- n )
 261     [ random-unit log e^ 1 swap - ] dip recip ^ ;
 262
 263 {
 264     { [ os windows? ] [ "random.windows" require ] }
 265     { [ os unix? ] [ "random.unix" require ] }
 266 } cond
 267
 268 "random.mersenne-twister" require