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