basis/random/random.factor

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