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