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
12 SYMBOL: system-random-generator
13 SYMBOL: secure-random-generator
14 SYMBOL: random-generator
16 GENERIC#: seed-random 1 ( obj seed -- obj )
17 GENERIC: random-32* ( obj -- n )
18 GENERIC: random-bytes* ( n obj -- byte-array )
20 M: object random-bytes*
21 [ integer>fixnum-strict [ (byte-array) ] keep ] 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
30 4 swap random-bytes* c:uint deref ;
32 ERROR: no-random-number-generator ;
34 M: no-random-number-generator summary
35 drop "Random number generator is not defined." ;
37 M: f random-bytes* no-random-number-generator ;
39 M: f random-32* no-random-number-generator ;
42 random-generator get random-32* ;
44 : random-bytes ( n -- byte-array )
45 random-generator get random-bytes* ;
49 :: (random-bits) ( numbits obj -- n )
51 obj random-32* numbits 32 - [ dup 32 > ] [
52 [ 32 shift obj random-32* + ] [ 32 - ] bi*
54 [ shift ] keep obj random-32* swap bits +
57 obj random-32* numbits bits
62 : random-bits ( numbits -- n )
63 random-generator get (random-bits) ;
65 : random-bits* ( numbits -- n )
66 1 - [ random-bits ] keep set-bit ;
70 : next-power-of-2-bits ( m -- numbits )
71 dup 2 <= [ drop 1 ] [ 1 - log2 1 + ] if ; inline
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
78 GENERIC#: (random-integer) 1 ( m obj -- n )
79 M: fixnum (random-integer) random-integer-loop ;
80 M: bignum (random-integer) random-integer-loop ;
82 : random-integer ( m -- n )
83 random-generator get (random-integer) ;
87 GENERIC: random ( obj -- elt )
90 [ f ] [ random-integer ] if-zero ;
94 [ length random-integer ] keep nth
97 M: assoc random >alist random ;
100 dup assoc-size [ drop f ] [
101 [ 0 ] [ array>> ] [ random ] tri* 1 + [
102 [ 2dup array-nth tombstone? [ 2 + ] 2dip ] loop
104 [ array-nth ] [ [ 1 + ] dip array-nth ] 2bi 2array
107 M: sets:set random members 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
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
123 : randomize ( seq -- randomized )
124 dup length randomize-n-last ;
126 ERROR: too-many-samples seq n ;
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 ;
133 : delete-random ( seq -- elt )
134 [ length random-integer ] keep
135 [ nth ] 2keep remove-nth! drop ;
137 : with-random ( obj quot -- )
138 random-generator swap with-variable ; inline
140 : with-system-random ( quot -- )
141 system-random-generator get swap with-random ; inline
143 : with-secure-random ( quot -- )
144 secure-random-generator get swap with-random ; inline
148 : (uniform-random-float) ( min max obj -- n )
149 [ random-32* ] keep random-32* [ >float ] bi@
151 [ over - 2.0 -64 ^ * ] dip
156 : uniform-random-float ( min max -- n )
157 random-generator get (uniform-random-float) ; inline
159 M: float random [ f ] [ 0.0 swap uniform-random-float ] if-zero ;
163 : (random-unit) ( obj -- n )
164 [ 0.0 1.0 ] dip (uniform-random-float) ; inline
168 : random-unit ( -- n )
169 random-generator get (random-unit) ; inline
171 : random-units ( length -- sequence )
172 random-generator get '[ _ (random-unit) ] replicate ;
174 : random-integers ( length n -- sequence )
175 random-generator get '[ _ _ (random-integer) ] replicate ;
179 : (cos-random-float) ( -- n )
180 0. 2pi uniform-random-float cos ;
182 : (log-sqrt-random-float) ( -- n )
183 random-unit log -2. * sqrt ;
187 : normal-random-float ( mean sigma -- n )
188 (cos-random-float) (log-sqrt-random-float) * * + ;
190 : lognormal-random-float ( mean sigma -- n )
191 normal-random-float e^ ;
193 : exponential-random-float ( lambda -- n )
194 random-unit log neg swap / ;
196 : weibull-random-float ( alpha beta -- n )
198 [ random-unit log neg ] dip
202 : pareto-random-float ( k alpha -- n )
203 [ random-unit ] dip recip ^ /f ;
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
216 0 :> r! 0 :> z! 0 :> result! ! initialize locals
219 [ 1. 4.5 log + + z 4.5 * - 0 >= ]
223 rnd (random-unit) :> u1
224 rnd (random-unit) :> u2
226 u1 1. u1 - / log ainv / :> v
234 : (gamma-random-float=1) ( alpha beta -- n )
235 nip random-unit log neg * ;
237 :: (gamma-random-float<1) ( alpha beta -- n )
238 ! Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
239 random-generator get :> rnd
242 0 :> x! 0 :> p! ! initialize locals
245 rnd (random-unit) x alpha 1 - ^ >
247 rnd (random-unit) x neg e^ >
250 rnd (random-unit) b * p!
254 b p - alpha / log neg
256 ] do while x beta * ;
260 : gamma-random-float ( alpha beta -- n )
262 { [ over 1 > ] [ (gamma-random-float>1) ] }
263 { [ over 1 = ] [ (gamma-random-float=1) ] }
264 [ (gamma-random-float<1) ]
267 : beta-random-float ( alpha beta -- n )
268 [ 1. gamma-random-float ] dip over zero?
269 [ 2drop 0 ] [ 1. gamma-random-float dupd + / ] if ;
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
277 2pi rnd (random-unit) *
279 4. kappa sq * 1. + sqrt 1. + :> a
280 a 2. a * sqrt - 2. kappa * / :> b
281 b sq 1. + 2. b * / :> r
283 0 :> c! 0 :> _f! ! initialize locals
286 [ 2. c - c * < ] [ 1. c - e^ c * <= ]
289 rnd (random-unit) pi * cos :> z
290 r z * 1. + r z + / _f!
295 rnd (random-unit) 0.5 > [ + ] [ - ] if
300 :: (triangular-random-float) ( low high mode -- n )
301 mode low - high low - / :> c!
304 u c > [ 1. u - u! 1. c - c! swap ] when
305 [ - u c * sqrt * ] keep + ;
309 : triangular-random-float ( low high -- n )
310 2dup + 2 /f (triangular-random-float) ;
312 : laplace-random-float ( mean scale -- n )
313 random-unit dup 0.5 <
314 [ 2 * log ] [ 1 swap - 2 * log neg ] if * + ;
316 : cauchy-random-float ( median scale -- n )
317 random-unit 0.5 - pi * tan * + ;
319 : chi-square-random-float ( dof -- n )
320 [ 0.5 ] dip 2 * gamma-random-float ;
322 : student-t-random-float ( dof -- n )
323 [ 0 1 normal-random-float ] dip
324 [ chi-square-random-float ] [ / ] bi sqrt / ;
326 : inv-gamma-random-float ( shape scale -- n )
327 recip gamma-random-float recip ;
329 : rayleigh-random-float ( mode -- n )
330 random-unit log -2 * sqrt * ;
332 : gumbel-random-float ( loc scale -- n )
333 random-unit log neg log * - ;
335 : logistic-random-float ( loc scale -- n )
336 random-unit dup 1 swap - / log * + ;
338 : power-random-float ( alpha -- n )
339 [ random-unit log e^ 1 swap - ] dip recip ^ ;
342 : poisson-random-float ( mean -- n )
343 [ -1 0 ] dip [ 2dup < ] random-generator get '[
344 [ 1 + ] 2dip [ _ (random-unit) log neg + ] dip
348 { [ os windows? ] [ "random.windows" require ] }
349 { [ os unix? ] [ "random.unix" require ] }
352 "random.mersenne-twister" require