|
7019
|
1 /* |
|
|
2 |
|
|
3 Copyright (C) 2006, 2007 John W. Eaton |
|
|
4 |
|
|
5 This file is part of Octave. |
|
|
6 |
|
|
7 Octave is free software; you can redistribute it and/or modify it |
|
|
8 under the terms of the GNU General Public License as published by the |
|
|
9 Free Software Foundation; either version 3 of the License, or (at your |
|
|
10 option) any later version. |
|
|
11 |
|
|
12 Octave is distributed in the hope that it will be useful, but WITHOUT |
|
|
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
|
15 for more details. |
|
|
16 |
|
|
17 You should have received a copy of the GNU General Public License |
|
|
18 along with Octave; see the file COPYING. If not, see |
|
|
19 <http://www.gnu.org/licenses/>. |
|
|
20 |
|
|
21 */ |
|
|
22 |
|
|
23 /* Original version written by Paul Kienzle distributed as free |
|
|
24 software in the in the public domain. */ |
|
5742
|
25 |
|
|
26 /* Needs the following defines: |
|
|
27 * NAN: value to return for Not-A-Number |
|
|
28 * RUNI: uniform generator on (0,1) |
|
|
29 * RNOR: normal generator |
|
|
30 * LGAMMA: log gamma function |
|
|
31 * INFINITE: function to test whether a value is infinite |
|
|
32 */ |
|
|
33 |
|
|
34 #if defined (HAVE_CONFIG_H) |
|
|
35 #include <config.h> |
|
|
36 #endif |
|
|
37 |
|
|
38 #include <math.h> |
|
|
39 #include <stdio.h> |
|
|
40 |
|
|
41 #include "f77-fcn.h" |
|
|
42 #include "lo-ieee.h" |
|
|
43 #include "lo-error.h" |
|
|
44 #include "randmtzig.h" |
|
|
45 #include "randpoisson.h" |
|
|
46 |
|
|
47 #undef NAN |
|
|
48 #define NAN octave_NaN |
|
6096
|
49 #undef INFINITE |
|
5742
|
50 #define INFINITE lo_ieee_isinf |
|
|
51 #define RUNI oct_randu() |
|
|
52 #define RNOR oct_randn() |
|
|
53 #define LGAMMA xlgamma |
|
|
54 |
|
|
55 F77_RET_T |
|
|
56 F77_FUNC (dlgams, DLGAMS) (const double *, double *, double *); |
|
|
57 |
|
|
58 static double |
|
|
59 xlgamma (double x) |
|
|
60 { |
|
|
61 double result; |
|
|
62 double sgngam; |
|
|
63 |
|
|
64 if (lo_ieee_isnan (x)) |
|
|
65 result = x; |
|
|
66 else if (x <= 0 || lo_ieee_isinf (x)) |
|
|
67 result = octave_Inf; |
|
|
68 else |
|
|
69 F77_XFCN (dlgams, DLGAMS, (&x, &result, &sgngam)); |
|
|
70 |
|
|
71 return result; |
|
|
72 } |
|
|
73 |
|
|
74 /* ---- pprsc.c from Stadloeber's winrand --- */ |
|
|
75 |
|
|
76 #include <math.h> |
|
|
77 |
|
|
78 /* flogfak(k) = ln(k!) */ |
|
|
79 static double |
|
|
80 flogfak (double k) |
|
|
81 { |
|
|
82 #define C0 9.18938533204672742e-01 |
|
|
83 #define C1 8.33333333333333333e-02 |
|
|
84 #define C3 -2.77777777777777778e-03 |
|
|
85 #define C5 7.93650793650793651e-04 |
|
|
86 #define C7 -5.95238095238095238e-04 |
|
|
87 |
|
|
88 static double logfak[30L] = { |
|
|
89 0.00000000000000000, 0.00000000000000000, 0.69314718055994531, |
|
|
90 1.79175946922805500, 3.17805383034794562, 4.78749174278204599, |
|
|
91 6.57925121201010100, 8.52516136106541430, 10.60460290274525023, |
|
|
92 12.80182748008146961, 15.10441257307551530, 17.50230784587388584, |
|
|
93 19.98721449566188615, 22.55216385312342289, 25.19122118273868150, |
|
|
94 27.89927138384089157, 30.67186010608067280, 33.50507345013688888, |
|
|
95 36.39544520803305358, 39.33988418719949404, 42.33561646075348503, |
|
|
96 45.38013889847690803, 48.47118135183522388, 51.60667556776437357, |
|
|
97 54.78472939811231919, 58.00360522298051994, 61.26170176100200198, |
|
|
98 64.55753862700633106, 67.88974313718153498, 71.25703896716800901 |
|
|
99 }; |
|
|
100 |
|
|
101 double r, rr; |
|
|
102 |
|
|
103 if (k >= 30.0) |
|
|
104 { |
|
|
105 r = 1.0 / k; |
|
|
106 rr = r * r; |
|
|
107 return ((k + 0.5)*log(k) - k + C0 + r*(C1 + rr*(C3 + rr*(C5 + rr*C7)))); |
|
|
108 } |
|
|
109 else |
|
|
110 return (logfak[(int)k]); |
|
|
111 } |
|
|
112 |
|
|
113 |
|
|
114 /****************************************************************** |
|
|
115 * * |
|
|
116 * Poisson Distribution - Patchwork Rejection/Inversion * |
|
|
117 * * |
|
|
118 ****************************************************************** |
|
|
119 * * |
|
|
120 * For parameter my < 10 Tabulated Inversion is applied. * |
|
|
121 * For my >= 10 Patchwork Rejection is employed: * |
|
|
122 * The area below the histogram function f(x) is rearranged in * |
|
|
123 * its body by certain point reflections. Within a large center * |
|
|
124 * interval variates are sampled efficiently by rejection from * |
|
|
125 * uniform hats. Rectangular immediate acceptance regions speed * |
|
|
126 * up the generation. The remaining tails are covered by * |
|
|
127 * exponential functions. * |
|
|
128 * * |
|
|
129 ****************************************************************** |
|
|
130 * * |
|
|
131 * FUNCTION : - pprsc samples a random number from the Poisson * |
|
|
132 * distribution with parameter my > 0. * |
|
|
133 * REFERENCE : - H. Zechner (1994): Efficient sampling from * |
|
|
134 * continuous and discrete unimodal distributions, * |
|
|
135 * Doctoral Dissertation, 156 pp., Technical * |
|
|
136 * University Graz, Austria. * |
|
|
137 * SUBPROGRAM : - drand(seed) ... (0,1)-Uniform generator with * |
|
|
138 * unsigned long integer *seed. * |
|
|
139 * * |
|
|
140 * Implemented by H. Zechner, January 1994 * |
|
|
141 * Revised by F. Niederl, July 1994 * |
|
|
142 * * |
|
|
143 ******************************************************************/ |
|
|
144 |
|
|
145 static double |
|
|
146 f (double k, double l_nu, double c_pm) |
|
|
147 { |
|
|
148 return exp(k * l_nu - flogfak(k) - c_pm); |
|
|
149 } |
|
|
150 |
|
|
151 static double |
|
|
152 pprsc (double my) |
|
|
153 { |
|
|
154 static double my_last = -1.0; |
|
|
155 static double m, k2, k4, k1, k5; |
|
|
156 static double dl, dr, r1, r2, r4, r5, ll, lr, l_my, c_pm, |
|
|
157 f1, f2, f4, f5, p1, p2, p3, p4, p5, p6; |
|
|
158 double Dk, X, Y; |
|
|
159 double Ds, U, V, W; |
|
|
160 |
|
|
161 if (my != my_last) |
|
|
162 { /* set-up */ |
|
|
163 my_last = my; |
|
|
164 /* approximate deviation of reflection points k2, k4 from my - 1/2 */ |
|
|
165 Ds = sqrt(my + 0.25); |
|
|
166 |
|
|
167 /* mode m, reflection points k2 and k4, and points k1 and k5, */ |
|
|
168 /* which delimit the centre region of h(x) */ |
|
|
169 m = floor(my); |
|
|
170 k2 = ceil(my - 0.5 - Ds); |
|
|
171 k4 = floor(my - 0.5 + Ds); |
|
|
172 k1 = k2 + k2 - m + 1L; |
|
|
173 k5 = k4 + k4 - m; |
|
|
174 |
|
|
175 /* range width of the critical left and right centre region */ |
|
|
176 dl = (k2 - k1); |
|
|
177 dr = (k5 - k4); |
|
|
178 |
|
|
179 /* recurrence constants r(k)=p(k)/p(k-1) at k = k1, k2, k4+1, k5+1 */ |
|
|
180 r1 = my / k1; |
|
|
181 r2 = my / k2; |
|
|
182 r4 = my / (k4 + 1.0); |
|
|
183 r5 = my / (k5 + 1.0); |
|
|
184 |
|
|
185 /* reciprocal values of the scale parameters of exp. tail envelope */ |
|
|
186 ll = log(r1); /* expon. tail left */ |
|
|
187 lr = -log(r5); /* expon. tail right*/ |
|
|
188 |
|
|
189 /* Poisson constants, necessary for computing function values f(k) */ |
|
|
190 l_my = log(my); |
|
|
191 c_pm = m * l_my - flogfak(m); |
|
|
192 |
|
|
193 /* function values f(k) = p(k)/p(m) at k = k2, k4, k1, k5 */ |
|
|
194 f2 = f(k2, l_my, c_pm); |
|
|
195 f4 = f(k4, l_my, c_pm); |
|
|
196 f1 = f(k1, l_my, c_pm); |
|
|
197 f5 = f(k5, l_my, c_pm); |
|
|
198 |
|
|
199 /* area of the two centre and the two exponential tail regions */ |
|
|
200 /* area of the two immediate acceptance regions between k2, k4 */ |
|
|
201 p1 = f2 * (dl + 1.0); /* immed. left */ |
|
|
202 p2 = f2 * dl + p1; /* centre left */ |
|
|
203 p3 = f4 * (dr + 1.0) + p2; /* immed. right */ |
|
|
204 p4 = f4 * dr + p3; /* centre right */ |
|
|
205 p5 = f1 / ll + p4; /* exp. tail left */ |
|
|
206 p6 = f5 / lr + p5; /* exp. tail right*/ |
|
|
207 } |
|
|
208 |
|
|
209 for (;;) |
|
|
210 { |
|
|
211 /* generate uniform number U -- U(0, p6) */ |
|
|
212 /* case distinction corresponding to U */ |
|
|
213 if ((U = RUNI * p6) < p2) |
|
|
214 { /* centre left */ |
|
|
215 |
|
|
216 /* immediate acceptance region |
|
|
217 R2 = [k2, m) *[0, f2), X = k2, ... m -1 */ |
|
|
218 if ((V = U - p1) < 0.0) return(k2 + floor(U/f2)); |
|
|
219 /* immediate acceptance region |
|
|
220 R1 = [k1, k2)*[0, f1), X = k1, ... k2-1 */ |
|
|
221 if ((W = V / dl) < f1 ) return(k1 + floor(V/f1)); |
|
|
222 |
|
|
223 /* computation of candidate X < k2, and its counterpart Y > k2 */ |
|
|
224 /* either squeeze-acceptance of X or acceptance-rejection of Y */ |
|
|
225 Dk = floor(dl * RUNI) + 1.0; |
|
|
226 if (W <= f2 - Dk * (f2 - f2/r2)) |
|
|
227 { /* quick accept of */ |
|
|
228 return(k2 - Dk); /* X = k2 - Dk */ |
|
|
229 } |
|
|
230 if ((V = f2 + f2 - W) < 1.0) |
|
|
231 { /* quick reject of Y*/ |
|
|
232 Y = k2 + Dk; |
|
|
233 if (V <= f2 + Dk * (1.0 - f2)/(dl + 1.0)) |
|
|
234 { /* quick accept of */ |
|
|
235 return(Y); /* Y = k2 + Dk */ |
|
|
236 } |
|
|
237 if (V <= f(Y, l_my, c_pm)) return(Y); /* final accept of Y*/ |
|
|
238 } |
|
|
239 X = k2 - Dk; |
|
|
240 } |
|
|
241 else if (U < p4) |
|
|
242 { /* centre right */ |
|
|
243 /* immediate acceptance region |
|
|
244 R3 = [m, k4+1)*[0, f4), X = m, ... k4 */ |
|
|
245 if ((V = U - p3) < 0.0) return(k4 - floor((U - p2)/f4)); |
|
|
246 /* immediate acceptance region |
|
|
247 R4 = [k4+1, k5+1)*[0, f5) */ |
|
|
248 if ((W = V / dr) < f5 ) return(k5 - floor(V/f5)); |
|
|
249 |
|
|
250 /* computation of candidate X > k4, and its counterpart Y < k4 */ |
|
|
251 /* either squeeze-acceptance of X or acceptance-rejection of Y */ |
|
|
252 Dk = floor(dr * RUNI) + 1.0; |
|
|
253 if (W <= f4 - Dk * (f4 - f4*r4)) |
|
|
254 { /* quick accept of */ |
|
|
255 return(k4 + Dk); /* X = k4 + Dk */ |
|
|
256 } |
|
|
257 if ((V = f4 + f4 - W) < 1.0) |
|
|
258 { /* quick reject of Y*/ |
|
|
259 Y = k4 - Dk; |
|
|
260 if (V <= f4 + Dk * (1.0 - f4)/ dr) |
|
|
261 { /* quick accept of */ |
|
|
262 return(Y); /* Y = k4 - Dk */ |
|
|
263 } |
|
|
264 if (V <= f(Y, l_my, c_pm)) return(Y); /* final accept of Y*/ |
|
|
265 } |
|
|
266 X = k4 + Dk; |
|
|
267 } |
|
|
268 else |
|
|
269 { |
|
|
270 W = RUNI; |
|
|
271 if (U < p5) |
|
|
272 { /* expon. tail left */ |
|
|
273 Dk = floor(1.0 - log(W)/ll); |
|
|
274 if ((X = k1 - Dk) < 0L) continue; /* 0 <= X <= k1 - 1 */ |
|
|
275 W *= (U - p4) * ll; /* W -- U(0, h(x)) */ |
|
|
276 if (W <= f1 - Dk * (f1 - f1/r1)) |
|
|
277 return(X); /* quick accept of X*/ |
|
|
278 } |
|
|
279 else |
|
|
280 { /* expon. tail right*/ |
|
|
281 Dk = floor(1.0 - log(W)/lr); |
|
|
282 X = k5 + Dk; /* X >= k5 + 1 */ |
|
|
283 W *= (U - p5) * lr; /* W -- U(0, h(x)) */ |
|
|
284 if (W <= f5 - Dk * (f5 - f5*r5)) |
|
|
285 return(X); /* quick accept of X*/ |
|
|
286 } |
|
|
287 } |
|
|
288 |
|
|
289 /* acceptance-rejection test of candidate X from the original area */ |
|
|
290 /* test, whether W <= f(k), with W = U*h(x) and U -- U(0, 1)*/ |
|
|
291 /* log f(X) = (X - m)*log(my) - log X! + log m! */ |
|
|
292 if (log(W) <= X * l_my - flogfak(X) - c_pm) return(X); |
|
|
293 } |
|
|
294 } |
|
|
295 /* ---- pprsc.c end ------ */ |
|
|
296 |
|
|
297 |
|
|
298 /* The remainder of the file is by Paul Kienzle */ |
|
|
299 |
|
|
300 /* Given uniform u, find x such that CDF(L,x)==u. Return x. */ |
|
|
301 static void |
|
|
302 poisson_cdf_lookup(double lambda, double *p, size_t n) |
|
|
303 { |
|
|
304 /* Table size is predicated on the maximum value of lambda |
|
|
305 * we want to store in the table, and the maximum value of |
|
|
306 * returned by the uniform random number generator on [0,1). |
|
|
307 * With lambda==10 and u_max = 1 - 1/(2^32+1), we |
|
|
308 * have poisson_pdf(lambda,36) < 1-u_max. If instead our |
|
|
309 * generator uses more bits of mantissa or returns a value |
|
|
310 * in the range [0,1], then for lambda==10 we need a table |
|
|
311 * size of 46 instead. For long doubles, the table size |
|
|
312 * will need to be longer still. */ |
|
|
313 #define TABLESIZE 46 |
|
|
314 double t[TABLESIZE]; |
|
|
315 |
|
|
316 /* Precompute the table for the u up to and including 0.458. |
|
|
317 * We will almost certainly need it. */ |
|
|
318 int intlambda = (int)floor(lambda); |
|
|
319 double P; |
|
|
320 int tableidx; |
|
|
321 size_t i = n; |
|
|
322 |
|
|
323 t[0] = P = exp(-lambda); |
|
|
324 for (tableidx = 1; tableidx <= intlambda; tableidx++) { |
|
|
325 P = P*lambda/(double)tableidx; |
|
|
326 t[tableidx] = t[tableidx-1] + P; |
|
|
327 } |
|
|
328 |
|
|
329 while (i-- > 0) { |
|
|
330 double u = RUNI; |
|
|
331 |
|
|
332 /* If u > 0.458 we know we can jump to floor(lambda) before |
|
|
333 * comparing (this observation is based on Stadlober's winrand |
|
|
334 * code). For lambda >= 1, this will be a win. Lambda < 1 |
|
|
335 * is already fast, so adding an extra comparison is not a |
|
|
336 * problem. */ |
|
|
337 int k = (u > 0.458 ? intlambda : 0); |
|
|
338 |
|
|
339 /* We aren't using a for loop here because when we find the |
|
|
340 * right k we want to jump to the next iteration of the |
|
|
341 * outer loop, and the continue statement will only work for |
|
|
342 * the inner loop. */ |
|
|
343 nextk: |
|
|
344 if ( u <= t[k] ) { |
|
|
345 p[i] = (double) k; |
|
|
346 continue; |
|
|
347 } |
|
|
348 if (++k < tableidx) goto nextk; |
|
|
349 |
|
|
350 /* We only need high values of the table very rarely so we |
|
|
351 * don't automatically compute the entire table. */ |
|
|
352 while (tableidx < TABLESIZE) { |
|
|
353 P = P*lambda/(double)tableidx; |
|
|
354 t[tableidx] = t[tableidx-1] + P; |
|
|
355 /* Make sure we converge to 1.0 just in case u is uniform |
|
|
356 * on [0,1] rather than [0,1). */ |
|
|
357 if (t[tableidx] == t[tableidx-1]) t[tableidx] = 1.0; |
|
|
358 tableidx++; |
|
|
359 if (u <= t[tableidx-1]) break; |
|
|
360 } |
|
|
361 |
|
|
362 /* We are assuming that the table size is big enough here. |
|
|
363 * This should be true even if RUNI is returning values in |
|
|
364 * the range [0,1] rather than [0,1). |
|
|
365 */ |
|
|
366 p[i] = (double)(tableidx-1); |
|
|
367 } |
|
|
368 } |
|
|
369 |
|
|
370 /* From Press, et al., Numerical Recipes */ |
|
|
371 static void |
|
|
372 poisson_rejection (double lambda, double *p, size_t n) |
|
|
373 { |
|
|
374 double sq = sqrt(2.0*lambda); |
|
|
375 double alxm = log(lambda); |
|
|
376 double g = lambda*alxm - LGAMMA(lambda+1.0); |
|
|
377 size_t i; |
|
|
378 |
|
|
379 for (i = 0; i < n; i++) |
|
|
380 { |
|
|
381 double y, em, t; |
|
|
382 do { |
|
|
383 do { |
|
|
384 y = tan(M_PI*RUNI); |
|
|
385 em = sq * y + lambda; |
|
|
386 } while (em < 0.0); |
|
|
387 em = floor(em); |
|
|
388 t = 0.9*(1.0+y*y)*exp(em*alxm-flogfak(em)-g); |
|
|
389 } while (RUNI > t); |
|
|
390 p[i] = em; |
|
|
391 } |
|
|
392 } |
|
|
393 |
|
|
394 /* The cutoff of L <= 1e8 in the following two functions before using |
|
|
395 * the normal approximation is based on: |
|
|
396 * > L=1e8; x=floor(linspace(0,2*L,1000)); |
|
|
397 * > max(abs(normal_pdf(x,L,L)-poisson_pdf(x,L))) |
|
|
398 * ans = 1.1376e-28 |
|
|
399 * For L=1e7, the max is around 1e-9, which is within the step size of RUNI. |
|
|
400 * For L>1e10 the pprsc function breaks down, as I saw from the histogram |
|
|
401 * of a large sample, so 1e8 is both small enough and large enough. */ |
|
|
402 |
|
|
403 /* Generate a set of poisson numbers with the same distribution */ |
|
|
404 void |
|
|
405 oct_fill_randp (double L, octave_idx_type n, double *p) |
|
|
406 { |
|
|
407 octave_idx_type i; |
|
|
408 if (L < 0.0 || INFINITE(L)) |
|
|
409 { |
|
|
410 for (i=0; i<n; i++) |
|
|
411 p[i] = NAN; |
|
|
412 } |
|
|
413 else if (L <= 10.0) |
|
|
414 { |
|
|
415 poisson_cdf_lookup(L, p, n); |
|
|
416 } |
|
|
417 else if (L <= 1e8) |
|
|
418 { |
|
|
419 for (i=0; i<n; i++) |
|
|
420 p[i] = pprsc(L); |
|
|
421 } |
|
|
422 else |
|
|
423 { |
|
|
424 /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */ |
|
|
425 const double sqrtL = sqrt(L); |
|
6198
|
426 for (i = 0; i < n; i++) |
|
5742
|
427 { |
|
|
428 p[i] = floor(RNOR*sqrtL + L + 0.5); |
|
|
429 if (p[i] < 0.0) |
|
|
430 p[i] = 0.0; /* will probably never happen */ |
|
|
431 } |
|
|
432 } |
|
|
433 } |
|
|
434 |
|
|
435 /* Generate one poisson variate */ |
|
|
436 double |
|
|
437 oct_randp (double L) |
|
|
438 { |
|
|
439 double ret; |
|
|
440 if (L < 0.0) ret = NAN; |
|
|
441 else if (L <= 12.0) { |
|
|
442 /* From Press, et al. Numerical recipes */ |
|
|
443 double g = exp(-L); |
|
|
444 int em = -1; |
|
|
445 double t = 1.0; |
|
|
446 do { |
|
|
447 ++em; |
|
|
448 t *= RUNI; |
|
|
449 } while (t > g); |
|
|
450 ret = em; |
|
|
451 } else if (L <= 1e8) { |
|
|
452 /* numerical recipes */ |
|
|
453 poisson_rejection(L, &ret, 1); |
|
|
454 } else if (INFINITE(L)) { |
|
5775
|
455 /* FIXME R uses NaN, but the normal approx. suggests that as |
|
5742
|
456 * limit should be inf. Which is correct? */ |
|
|
457 ret = NAN; |
|
|
458 } else { |
|
|
459 /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */ |
|
|
460 ret = floor(RNOR*sqrt(L) + L + 0.5); |
|
|
461 if (ret < 0.0) ret = 0.0; /* will probably never happen */ |
|
|
462 } |
|
|
463 return ret; |
|
|
464 } |
|
|
465 |
|
|
466 /* |
|
|
467 ;;; Local Variables: *** |
|
|
468 ;;; mode: C *** |
|
|
469 ;;; End: *** |
|
|
470 */ |
