basis/random/random.factor

   1 ! Copyright (C) 2008 Doug Coleman.
   2 ! See https://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 IN: random
  10
  11 USE: kernel.private
  12
  13 SYMBOL: system-random-generator
  14 SYMBOL: secure-random-generator
  15 SYMBOL: random-generator
  16
  17 GENERIC#: seed-random 1 ( rnd seed -- rnd )
  18 GENERIC: random-32* ( rnd -- n )
  19 GENERIC: random-bytes* ( n rnd -- 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 rnd -- n )
  51     numbits 32 > [
  52         rnd random-32* numbits 32 - [ dup 32 > ] [
  53             [ 32 shift rnd random-32* + ] [ 32 - ] bi*
  54         ] while [
  55             [ shift ] keep rnd random-32* swap bits +
  56         ] unless-zero
  57     ] [
  58         rnd 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 GENERIC#: random* 1 ( obj rnd -- elt )
  70
  71 : random ( obj -- elt )
  72     random-generator get random* ;
  73
  74 : randoms ( length obj -- seq )
  75     random-generator get '[ _ _ random* ] replicate ;
  76
  77 <PRIVATE
  78
  79 : next-power-of-2-bits ( m -- numbits )
  80     dup 2 <= [ drop 1 ] [ 1 - log2 1 + ] if ; inline
  81
  82 :: random-integer ( m rnd -- n )
  83     m zero? [ f ] [
  84         rnd random-32* { integer } declare 32 m next-power-of-2-bits 32 - [ dup 0 > ] [
  85             [ 32 shift rnd random-32* { integer } declare + ] [ 32 + ] [ 32 - ] tri*
  86         ] while drop [ m * ] [ neg shift ] bi*
  87     ] if ; inline
  88
  89 PRIVATE>
  90
  91 M: fixnum random* random-integer ;
  92
  93 M: bignum random* random-integer ;
  94
  95 M: sequence random*
  96     [ f ] swap '[ [ length _ random* ] keep nth ] if-empty ;
  97
  98 M: assoc random* [ >alist ] dip random* ;
  99
 100 M: hashtable random*
 101     [ dup assoc-size [ drop f ] ] dip '[
 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 ] dip random* ;
 109
 110 M: hash-set random*
 111     [ dup cardinality [ drop f ] ] dip '[
 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* ] [ 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 ] keep [ nth ] 2keep remove-nth! drop ;
 136
 137 : with-random ( rnd 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 rnd -- 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*
 160     [ f ] swap '[ 0.0 _ (uniform-random-float) ] if-zero ; inline
 161
 162 <PRIVATE
 163
 164 ! XXX: rename to random-unit*
 165 : (random-unit) ( rnd -- n )
 166     [ 0.0 1.0 ] dip (uniform-random-float) ; inline
 167
 168 PRIVATE>
 169
 170 : random-unit ( -- n )
 171     random-generator get (random-unit) ; inline
 172
 173 : random-units ( length -- sequence )
 174     random-generator get '[ _ (random-unit) ] replicate ;
 175
 176 <PRIVATE
 177
 178 : (cos-random-float) ( -- n )
 179     0. 2pi uniform-random-float cos ;
 180
 181 : (log-sqrt-random-float) ( -- n )
 182     random-unit log -2. * sqrt ;
 183
 184 PRIVATE>
 185
 186 : normal-random-float ( mean sigma -- n )
 187     (cos-random-float) (log-sqrt-random-float) * * + ;
 188
 189 : lognormal-random-float ( mean sigma -- n )
 190     normal-random-float e^ ;
 191
 192 : exponential-random-float ( lambda -- n )
 193     random-unit log neg swap / ;
 194
 195 : weibull-random-float ( alpha beta -- n )
 196     [
 197         [ random-unit log neg ] dip
 198         1. swap / ^
 199     ] dip * ;
 200
 201 : pareto-random-float ( k alpha -- n )
 202     [ random-unit ] dip recip ^ /f ;
 203
 204 <PRIVATE
 205
 206 :: (gamma-random-float>1) ( alpha beta -- n )
 207     ! Uses R.C.H. Cheng, "The generation of Gamma
 208     ! variables with non-integral shape parameters",
 209     ! Applied Statistics, (1977), 26, No. 1, p71-74
 210     random-generator get :> rnd
 211     2. alpha * 1 - sqrt  :> ainv
 212     alpha 4. log -       :> bbb
 213     alpha ainv +         :> ccc
 214
 215     0 :> r! 0 :> z! 0 :> result! ! initialize locals
 216     [
 217         r {
 218             [ 1. 4.5 log + + z 4.5 * - 0 >= ]
 219             [ z log >= ]
 220         } 1|| not
 221     ] [
 222         rnd (random-unit) :> u1
 223         rnd (random-unit) :> u2
 224
 225         u1 1. u1 - / log ainv / :> v
 226         alpha v e^ *            :> x
 227         u1 sq u2 *              z!
 228         bbb ccc v * + x -       r!
 229
 230         x beta *                result!
 231     ] do while result ;
 232
 233 : (gamma-random-float=1) ( alpha beta -- n )
 234     nip random-unit log neg * ;
 235
 236 :: (gamma-random-float<1) ( alpha beta -- n )
 237     ! Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
 238     random-generator get :> rnd
 239     alpha e + e / :> b
 240
 241     0 :> x! 0 :> p! ! initialize locals
 242     [
 243         p 1.0 > [
 244             rnd (random-unit) x alpha 1 - ^ >
 245         ] [
 246             rnd (random-unit) x neg e^ >
 247         ] if
 248     ] [
 249         rnd (random-unit) b * p!
 250         p 1.0 <= [
 251             p 1. alpha / ^
 252         ] [
 253             b p - alpha / log neg
 254         ] if x!
 255     ] do while x beta * ;
 256
 257 PRIVATE>
 258
 259 : gamma-random-float ( alpha beta -- n )
 260     {
 261         { [ over 1 > ] [ (gamma-random-float>1) ] }
 262         { [ over 1 = ] [ (gamma-random-float=1) ] }
 263         [ (gamma-random-float<1) ]
 264     } cond ;
 265
 266 : beta-random-float ( alpha beta -- n )
 267     [ 1. gamma-random-float ] dip over zero?
 268     [ 2drop 0 ] [ 1. gamma-random-float dupd + / ] if ;
 269
 270 :: von-mises-random-float ( mu kappa -- n )
 271     ! Based upon an algorithm published in: Fisher, N.I.,
 272     ! "Statistical Analysis of Circular Data", Cambridge
 273     ! University Press, 1993.
 274     random-generator get :> rnd
 275     kappa 1e-6 <= [
 276         2pi rnd (random-unit) *
 277     ] [
 278         4. kappa sq * 1. + sqrt 1. + :> a
 279         a 2. a * sqrt - 2. kappa * / :> b
 280         b sq 1. + 2. b * /           :> r
 281
 282         0 :> c! 0 :> _f! ! initialize locals
 283         [
 284             rnd (random-unit) {
 285                 [ 2. c - c * < ] [ 1. c - e^ c * <= ]
 286             } 1|| not
 287         ] [
 288             rnd (random-unit) pi * cos :> z
 289             r z * 1. + r z + /   _f!
 290             r _f - kappa *       c!
 291         ] do while
 292
 293         mu 2pi mod _f cos
 294         rnd (random-unit) 0.5 > [ + ] [ - ] if
 295     ] if ;
 296
 297 <PRIVATE
 298
 299 :: (triangular-random-float) ( low high mode -- n )
 300     mode low - high low - / :> c!
 301     random-unit :> u!
 302     high low
 303     u c > [ 1. u - u! 1. c - c! swap ] when
 304     [ - u c * sqrt * ] keep + ;
 305
 306 PRIVATE>
 307
 308 : triangular-random-float ( low high -- n )
 309     2dup + 2 /f (triangular-random-float) ;
 310
 311 : laplace-random-float ( mean scale -- n )
 312     random-unit dup 0.5 <
 313     [ 2 * log ] [ 1 swap - 2 * log neg ] if * + ;
 314
 315 : cauchy-random-float ( median scale -- n )
 316     random-unit 0.5 - pi * tan * + ;
 317
 318 : chi-square-random-float ( dof -- n )
 319     [ 0.5 ] dip 2 * gamma-random-float ;
 320
 321 : student-t-random-float ( dof -- n )
 322     [ 0 1 normal-random-float ] dip
 323     [ chi-square-random-float ] [ / ] bi sqrt / ;
 324
 325 : inv-gamma-random-float ( shape scale -- n )
 326     recip gamma-random-float recip ;
 327
 328 : rayleigh-random-float ( mode -- n )
 329     random-unit log -2 * sqrt * ;
 330
 331 : gumbel-random-float ( loc scale -- n )
 332     random-unit log neg log * - ;
 333
 334 : logistic-random-float ( loc scale -- n )
 335     random-unit dup 1 swap - / log * + ;
 336
 337 : power-random-float ( alpha -- n )
 338     [ random-unit log e^ 1 swap - ] dip recip ^ ;
 339
 340 ! Box-Muller
 341 : poisson-random-float ( mean -- n )
 342     [ -1 0 ] dip [ 2dup < ] random-generator get '[
 343         [ 1 + ] 2dip [ _ (random-unit) log neg + ] dip
 344     ] while 2drop ;
 345
 346 :: binomial-random ( n p -- x )
 347     n assert-non-negative drop
 348     p 0.0 1.0 between? [
 349         {
 350             { [ p 0.0 = ] [ 0 ] }
 351             { [ p 1.0 = ] [ n ] }
 352             { [ n 1 = ] [ random-unit p < 1 0 ? ] }
 353             { [ p 0.5 > ] [ n dup 1.0 p - binomial-random - ] }
 354             { [ n p * 10.0 < ] [
 355                 ! BG: Geometric method by Devroye with running time of O(n*p).
 356                 ! https://dl.acm.org/doi/pdf/10.1145/42372.42381
 357                 1.0 p - log :> c
 358                 0 0 random-generator get '[
 359                     _ (random-unit) log c /i 1 + +
 360                     dup n <= dup [ [ 1 + ] 2dip ] when
 361                 ] loop drop
 362             ] }
 363             [
 364                 ! BTRS: Transformed rejection with squeeze method by Wolfgang Hörmann
 365                 ! https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.8407&rep=rep1&type=pdf
 366                 n p * 10.0 >= p 0.5 <= and t assert=
 367                 random-generator get :> rnd
 368
 369                 n p * 1.0 p - * sqrt :> spq
 370                 1.15 2.53 spq * + :> b
 371                 -0.0873 0.0248 b * + 0.01 p * + :> a
 372                 n p * 0.5 + :> c
 373                 0.92 4.2 b / - :> vr
 374
 375                 2.83 5.1 b / + spq * :> alpha
 376                 p 1.0 p - / log :> lpq
 377                 n 1 + p * floor :> m
 378                 m 1 + lgamma n m - 1 + lgamma + :> h
 379
 380                 f [
 381                     rnd (random-unit) 0.5 - :> u
 382                     rnd (random-unit) :> v
 383                     0.5 u abs - :> us
 384                     drop 2.0 a us / * b + u * c + floor >integer dup :> k
 385                     k 0 n between? [
 386                         { [ us 0.07 >= ] [ v vr <= ] } 0&& [ f ] [
 387                             alpha a us sq / b + / v * log
 388                             h k 1 + lgamma - n k - 1 +
 389                             lgamma - k m - lpq * + >
 390                         ] if
 391                     ] [ t ] if
 392                 ] loop
 393             ]
 394         } cond
 395     ] [
 396         "p must be in the range 0.0 <= p <= 1.0" throw
 397     ] if ;
 398
 399 {
 400     { [ os windows? ] [ "random.windows" require ] }
 401     { [ os unix? ] [ "random.unix" require ] }
 402 } cond
 403
 404 "random.mersenne-twister" require