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