GNU Octave  4.4.1
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
randpoisson.cc
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2006-2018 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
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11 
12 Octave is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License 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 <https://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. */
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 <cmath>
39 #include <cstddef>
40 
41 #include "f77-fcn.h"
42 #include "lo-error.h"
43 #include "lo-ieee.h"
44 #include "randmtzig.h"
45 #include "randpoisson.h"
46 
47 #undef INFINITE
48 #define INFINITE lo_ieee_isinf
49 #define RUNI oct_randu()
50 #define RNOR oct_randn()
51 #define LGAMMA xlgamma
52 
53 static double
54 xlgamma (double x)
55 {
56  return std::lgamma (x);
57 }
58 
59 /* ---- pprsc.c from Stadloeber's winrand --- */
60 
61 /* flogfak(k) = ln(k!) */
62 static double
63 flogfak (double k)
64 {
65 #define C0 9.18938533204672742e-01
66 #define C1 8.33333333333333333e-02
67 #define C3 -2.77777777777777778e-03
68 #define C5 7.93650793650793651e-04
69 #define C7 -5.95238095238095238e-04
70 
71  static double logfak[30L] =
72  {
73  0.00000000000000000, 0.00000000000000000, 0.69314718055994531,
74  1.79175946922805500, 3.17805383034794562, 4.78749174278204599,
75  6.57925121201010100, 8.52516136106541430, 10.60460290274525023,
76  12.80182748008146961, 15.10441257307551530, 17.50230784587388584,
77  19.98721449566188615, 22.55216385312342289, 25.19122118273868150,
78  27.89927138384089157, 30.67186010608067280, 33.50507345013688888,
79  36.39544520803305358, 39.33988418719949404, 42.33561646075348503,
80  45.38013889847690803, 48.47118135183522388, 51.60667556776437357,
81  54.78472939811231919, 58.00360522298051994, 61.26170176100200198,
82  64.55753862700633106, 67.88974313718153498, 71.25703896716800901
83  };
84 
85  double r, rr;
86 
87  if (k >= 30.0)
88  {
89  r = 1.0 / k;
90  rr = r * r;
91  return ((k + 0.5)*std::log (k) - k + C0
92  + r*(C1 + rr*(C3 + rr*(C5 + rr*C7))));
93  }
94  else
95  return (logfak[static_cast<int> (k)]);
96 }
97 
98 /******************************************************************
99  * *
100  * Poisson Distribution - Patchwork Rejection/Inversion *
101  * *
102  ******************************************************************
103  * *
104  * For parameter my < 10, Tabulated Inversion is applied. *
105  * For my >= 10, Patchwork Rejection is employed: *
106  * The area below the histogram function f(x) is rearranged in *
107  * its body by certain point reflections. Within a large center *
108  * interval variates are sampled efficiently by rejection from *
109  * uniform hats. Rectangular immediate acceptance regions speed *
110  * up the generation. The remaining tails are covered by *
111  * exponential functions. *
112  * *
113  ******************************************************************
114  * *
115  * FUNCTION : - pprsc samples a random number from the Poisson *
116  * distribution with parameter my > 0. *
117  * REFERENCE : - H. Zechner (1994): Efficient sampling from *
118  * continuous and discrete unimodal distributions, *
119  * Doctoral Dissertation, 156 pp., Technical *
120  * University Graz, Austria. *
121  * SUBPROGRAM : - drand(seed) ... (0,1)-Uniform generator with *
122  * unsigned long integer *seed. *
123  * *
124  * Implemented by H. Zechner, January 1994 *
125  * Revised by F. Niederl, July 1994 *
126  * *
127  ******************************************************************/
128 
129 static double
130 f (double k, double l_nu, double c_pm)
131 {
132  return exp (k * l_nu - flogfak (k) - c_pm);
133 }
134 
135 static double
136 pprsc (double my)
137 {
138  static double my_last = -1.0;
139  static double m, k2, k4, k1, k5;
140  static double dl, dr, r1, r2, r4, r5, ll, lr, l_my, c_pm,
141  f1, f2, f4, f5, p1, p2, p3, p4, p5, p6;
142  double Dk, X, Y;
143  double Ds, U, V, W;
144 
145  if (my != my_last)
146  { /* set-up */
147  my_last = my;
148  /* approximate deviation of reflection points k2, k4 from my - 1/2 */
149  Ds = std::sqrt (my + 0.25);
150 
151  /* mode m, reflection points k2 and k4, and points k1 and k5, */
152  /* which delimit the centre region of h(x) */
153  m = std::floor (my);
154  k2 = ceil (my - 0.5 - Ds);
155  k4 = std::floor (my - 0.5 + Ds);
156  k1 = k2 + k2 - m + 1L;
157  k5 = k4 + k4 - m;
158 
159  /* range width of the critical left and right centre region */
160  dl = (k2 - k1);
161  dr = (k5 - k4);
162 
163  /* recurrence constants r(k)=p(k)/p(k-1) at k = k1, k2, k4+1, k5+1 */
164  r1 = my / k1;
165  r2 = my / k2;
166  r4 = my / (k4 + 1.0);
167  r5 = my / (k5 + 1.0);
168 
169  /* reciprocal values of the scale parameters of exp. tail envelope */
170  ll = std::log (r1); /* expon. tail left */
171  lr = -std::log (r5); /* expon. tail right*/
172 
173  /* Poisson constants, necessary for computing function values f(k) */
174  l_my = std::log (my);
175  c_pm = m * l_my - flogfak (m);
176 
177  /* function values f(k) = p(k)/p(m) at k = k2, k4, k1, k5 */
178  f2 = f (k2, l_my, c_pm);
179  f4 = f (k4, l_my, c_pm);
180  f1 = f (k1, l_my, c_pm);
181  f5 = f (k5, l_my, c_pm);
182 
183  /* area of the two centre and the two exponential tail regions */
184  /* area of the two immediate acceptance regions between k2, k4 */
185  p1 = f2 * (dl + 1.0); /* immed. left */
186  p2 = f2 * dl + p1; /* centre left */
187  p3 = f4 * (dr + 1.0) + p2; /* immed. right */
188  p4 = f4 * dr + p3; /* centre right */
189  p5 = f1 / ll + p4; /* exp. tail left */
190  p6 = f5 / lr + p5; /* exp. tail right*/
191  }
192 
193  for (;;)
194  {
195  /* generate uniform number U -- U(0, p6) */
196  /* case distinction corresponding to U */
197  if ((U = RUNI * p6) < p2)
198  { /* centre left */
199 
200  /* immediate acceptance region
201  R2 = [k2, m) *[0, f2), X = k2, ... m -1 */
202  if ((V = U - p1) < 0.0) return (k2 + std::floor (U/f2));
203  /* immediate acceptance region
204  R1 = [k1, k2)*[0, f1), X = k1, ... k2-1 */
205  if ((W = V / dl) < f1 ) return (k1 + std::floor (V/f1));
206 
207  /* computation of candidate X < k2, and its counterpart Y > k2 */
208  /* either squeeze-acceptance of X or acceptance-rejection of Y */
209  Dk = std::floor (dl * RUNI) + 1.0;
210  if (W <= f2 - Dk * (f2 - f2/r2))
211  { /* quick accept of */
212  return (k2 - Dk); /* X = k2 - Dk */
213  }
214  if ((V = f2 + f2 - W) < 1.0)
215  { /* quick reject of Y*/
216  Y = k2 + Dk;
217  if (V <= f2 + Dk * (1.0 - f2)/(dl + 1.0))
218  { /* quick accept of */
219  return (Y); /* Y = k2 + Dk */
220  }
221  if (V <= f (Y, l_my, c_pm)) return (Y); /* final accept of Y*/
222  }
223  X = k2 - Dk;
224  }
225  else if (U < p4)
226  { /* centre right */
227  /* immediate acceptance region
228  R3 = [m, k4+1)*[0, f4), X = m, ... k4 */
229  if ((V = U - p3) < 0.0) return (k4 - std::floor ((U - p2)/f4));
230  /* immediate acceptance region
231  R4 = [k4+1, k5+1)*[0, f5) */
232  if ((W = V / dr) < f5 ) return (k5 - std::floor (V/f5));
233 
234  /* computation of candidate X > k4, and its counterpart Y < k4 */
235  /* either squeeze-acceptance of X or acceptance-rejection of Y */
236  Dk = std::floor (dr * RUNI) + 1.0;
237  if (W <= f4 - Dk * (f4 - f4*r4))
238  { /* quick accept of */
239  return (k4 + Dk); /* X = k4 + Dk */
240  }
241  if ((V = f4 + f4 - W) < 1.0)
242  { /* quick reject of Y*/
243  Y = k4 - Dk;
244  if (V <= f4 + Dk * (1.0 - f4)/ dr)
245  { /* quick accept of */
246  return (Y); /* Y = k4 - Dk */
247  }
248  if (V <= f (Y, l_my, c_pm)) return (Y); /* final accept of Y*/
249  }
250  X = k4 + Dk;
251  }
252  else
253  {
254  W = RUNI;
255  if (U < p5)
256  { /* expon. tail left */
257  Dk = std::floor (1.0 - std::log (W)/ll);
258  if ((X = k1 - Dk) < 0L) continue; /* 0 <= X <= k1 - 1 */
259  W *= (U - p4) * ll; /* W -- U(0, h(x)) */
260  if (W <= f1 - Dk * (f1 - f1/r1))
261  return (X); /* quick accept of X*/
262  }
263  else
264  { /* expon. tail right*/
265  Dk = std::floor (1.0 - std::log (W)/lr);
266  X = k5 + Dk; /* X >= k5 + 1 */
267  W *= (U - p5) * lr; /* W -- U(0, h(x)) */
268  if (W <= f5 - Dk * (f5 - f5*r5))
269  return (X); /* quick accept of X*/
270  }
271  }
272 
273  /* acceptance-rejection test of candidate X from the original area */
274  /* test, whether W <= f(k), with W = U*h(x) and U -- U(0, 1)*/
275  /* log f(X) = (X - m)*log(my) - log X! + log m! */
276  if (std::log (W) <= X * l_my - flogfak (X) - c_pm) return (X);
277  }
278 }
279 /* ---- pprsc.c end ------ */
280 
281 /* The remainder of the file is by Paul Kienzle */
282 
283 /* Given uniform u, find x such that CDF(L,x)==u. Return x. */
284 static void
285 poisson_cdf_lookup (double lambda, double *p, size_t n)
286 {
287  /* Table size is predicated on the maximum value of lambda
288  * we want to store in the table, and the maximum value of
289  * returned by the uniform random number generator on [0,1).
290  * With lambda==10 and u_max = 1 - 1/(2^32+1), we
291  * have poisson_pdf(lambda,36) < 1-u_max. If instead our
292  * generator uses more bits of mantissa or returns a value
293  * in the range [0,1], then for lambda==10 we need a table
294  * size of 46 instead. For long doubles, the table size
295  * will need to be longer still. */
296 #define TABLESIZE 46
297  double t[TABLESIZE];
298 
299  /* Precompute the table for the u up to and including 0.458.
300  * We will almost certainly need it. */
301  int intlambda = static_cast<int> (std::floor (lambda));
302  double P;
303  int tableidx;
304  size_t i = n;
305 
306  t[0] = P = exp (-lambda);
307  for (tableidx = 1; tableidx <= intlambda; tableidx++)
308  {
309  P = P*lambda/static_cast<double> (tableidx);
310  t[tableidx] = t[tableidx-1] + P;
311  }
312 
313  while (i-- > 0)
314  {
315  double u = RUNI;
316 
317  /* If u > 0.458 we know we can jump to floor(lambda) before
318  * comparing (this observation is based on Stadlober's winrand
319  * code). For lambda >= 1, this will be a win. Lambda < 1
320  * is already fast, so adding an extra comparison is not a
321  * problem. */
322  int k = (u > 0.458 ? intlambda : 0);
323 
324  /* We aren't using a for loop here because when we find the
325  * right k we want to jump to the next iteration of the
326  * outer loop, and the continue statement will only work for
327  * the inner loop. */
328  nextk:
329  if (u <= t[k])
330  {
331  p[i] = static_cast<double> (k);
332  continue;
333  }
334  if (++k < tableidx)
335  goto nextk;
336 
337  /* We only need high values of the table very rarely so we
338  * don't automatically compute the entire table. */
339  while (tableidx < TABLESIZE)
340  {
341  P = P*lambda/static_cast<double> (tableidx);
342  t[tableidx] = t[tableidx-1] + P;
343  /* Make sure we converge to 1.0 just in case u is uniform
344  * on [0,1] rather than [0,1). */
345  if (t[tableidx] == t[tableidx-1]) t[tableidx] = 1.0;
346  tableidx++;
347  if (u <= t[tableidx-1]) break;
348  }
349 
350  /* We are assuming that the table size is big enough here.
351  * This should be true even if RUNI is returning values in
352  * the range [0,1] rather than [0,1). */
353  p[i] = static_cast<double> (tableidx-1);
354  }
355 }
356 
357 static void
358 poisson_cdf_lookup_float (double lambda, float *p, size_t n)
359 {
360  double t[TABLESIZE];
361 
362  /* Precompute the table for the u up to and including 0.458.
363  * We will almost certainly need it. */
364  int intlambda = static_cast<int> (std::floor (lambda));
365  double P;
366  int tableidx;
367  size_t i = n;
368 
369  t[0] = P = exp (-lambda);
370  for (tableidx = 1; tableidx <= intlambda; tableidx++)
371  {
372  P = P*lambda/static_cast<double> (tableidx);
373  t[tableidx] = t[tableidx-1] + P;
374  }
375 
376  while (i-- > 0)
377  {
378  double u = RUNI;
379  int k = (u > 0.458 ? intlambda : 0);
380  nextk:
381  if (u <= t[k])
382  {
383  p[i] = static_cast<float> (k);
384  continue;
385  }
386  if (++k < tableidx)
387  goto nextk;
388 
389  while (tableidx < TABLESIZE)
390  {
391  P = P*lambda/static_cast<double> (tableidx);
392  t[tableidx] = t[tableidx-1] + P;
393  if (t[tableidx] == t[tableidx-1]) t[tableidx] = 1.0;
394  tableidx++;
395  if (u <= t[tableidx-1]) break;
396  }
397 
398  p[i] = static_cast<float> (tableidx-1);
399  }
400 }
401 
402 /* From Press, et al., Numerical Recipes */
403 static void
404 poisson_rejection (double lambda, double *p, size_t n)
405 {
406  double sq = std::sqrt (2.0*lambda);
407  double alxm = std::log (lambda);
408  double g = lambda*alxm - LGAMMA(lambda+1.0);
409  size_t i;
410 
411  for (i = 0; i < n; i++)
412  {
413  double y, em, t;
414  do
415  {
416  do
417  {
418  y = tan (M_PI*RUNI);
419  em = sq * y + lambda;
420  } while (em < 0.0);
421  em = std::floor (em);
422  t = 0.9*(1.0+y*y)*exp (em*alxm-flogfak (em)-g);
423  } while (RUNI > t);
424  p[i] = em;
425  }
426 }
427 
428 /* From Press, et al., Numerical Recipes */
429 static void
430 poisson_rejection_float (double lambda, float *p, size_t n)
431 {
432  double sq = std::sqrt (2.0*lambda);
433  double alxm = std::log (lambda);
434  double g = lambda*alxm - LGAMMA(lambda+1.0);
435  size_t i;
436 
437  for (i = 0; i < n; i++)
438  {
439  double y, em, t;
440  do
441  {
442  do
443  {
444  y = tan (M_PI*RUNI);
445  em = sq * y + lambda;
446  } while (em < 0.0);
447  em = std::floor (em);
448  t = 0.9*(1.0+y*y)*exp (em*alxm-flogfak (em)-g);
449  } while (RUNI > t);
450  p[i] = em;
451  }
452 }
453 
454 /* The cutoff of L <= 1e8 in the following two functions before using
455  * the normal approximation is based on:
456  * > L=1e8; x=floor(linspace(0,2*L,1000));
457  * > max(abs(normal_pdf(x,L,L)-poisson_pdf(x,L)))
458  * ans = 1.1376e-28
459  * For L=1e7, the max is around 1e-9, which is within the step size of RUNI.
460  * For L>1e10 the pprsc function breaks down, as I saw from the histogram
461  * of a large sample, so 1e8 is both small enough and large enough. */
462 
463 /* Generate a set of poisson numbers with the same distribution */
464 void
465 oct_fill_randp (double L, octave_idx_type n, double *p)
466 {
468  if (L < 0.0 || INFINITE(L))
469  {
470  for (i=0; i<n; i++)
472  }
473  else if (L <= 10.0)
474  {
475  poisson_cdf_lookup (L, p, n);
476  }
477  else if (L <= 1e8)
478  {
479  for (i=0; i<n; i++)
480  p[i] = pprsc (L);
481  }
482  else
483  {
484  /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */
485  const double sqrtL = std::sqrt (L);
486  for (i = 0; i < n; i++)
487  {
488  p[i] = std::floor (RNOR*sqrtL + L + 0.5);
489  if (p[i] < 0.0)
490  p[i] = 0.0; /* will probably never happen */
491  }
492  }
493 }
494 
495 /* Generate one poisson variate */
496 double
497 oct_randp (double L)
498 {
499  double ret;
500  if (L < 0.0) ret = octave::numeric_limits<double>::NaN ();
501  else if (L <= 12.0)
502  {
503  /* From Press, et al. Numerical recipes */
504  double g = exp (-L);
505  int em = -1;
506  double t = 1.0;
507  do
508  {
509  ++em;
510  t *= RUNI;
511  } while (t > g);
512  ret = em;
513  }
514  else if (L <= 1e8)
515  {
516  /* numerical recipes */
517  poisson_rejection (L, &ret, 1);
518  }
519  else if (INFINITE(L))
520  {
521  /* FIXME: R uses NaN, but the normal approximation suggests that
522  * limit should be Inf. Which is correct? */
524  }
525  else
526  {
527  /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */
528  ret = std::floor (RNOR*std::sqrt (L) + L + 0.5);
529  if (ret < 0.0) ret = 0.0; /* will probably never happen */
530  }
531  return ret;
532 }
533 
534 /* Generate a set of poisson numbers with the same distribution */
535 void
537 {
538  double L = FL;
540  if (L < 0.0 || INFINITE(L))
541  {
542  for (i=0; i<n; i++)
544  }
545  else if (L <= 10.0)
546  {
547  poisson_cdf_lookup_float (L, p, n);
548  }
549  else if (L <= 1e8)
550  {
551  for (i=0; i<n; i++)
552  p[i] = pprsc (L);
553  }
554  else
555  {
556  /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */
557  const double sqrtL = std::sqrt (L);
558  for (i = 0; i < n; i++)
559  {
560  p[i] = std::floor (RNOR*sqrtL + L + 0.5);
561  if (p[i] < 0.0)
562  p[i] = 0.0; /* will probably never happen */
563  }
564  }
565 }
566 
567 /* Generate one poisson variate */
568 float
569 oct_float_randp (float FL)
570 {
571  double L = FL;
572  float ret;
573  if (L < 0.0) ret = octave::numeric_limits<float>::NaN ();
574  else if (L <= 12.0)
575  {
576  /* From Press, et al. Numerical recipes */
577  double g = exp (-L);
578  int em = -1;
579  double t = 1.0;
580  do
581  {
582  ++em;
583  t *= RUNI;
584  } while (t > g);
585  ret = em;
586  }
587  else if (L <= 1e8)
588  {
589  /* numerical recipes */
590  poisson_rejection_float (L, &ret, 1);
591  }
592  else if (INFINITE(L))
593  {
594  /* FIXME: R uses NaN, but the normal approximation suggests that
595  * limit should be Inf. Which is correct? */
597  }
598  else
599  {
600  /* normal approximation: from Phys. Rev. D (1994) v50 p1284 */
601  ret = std::floor (RNOR*std::sqrt (L) + L + 0.5);
602  if (ret < 0.0) ret = 0.0; /* will probably never happen */
603  }
604  return ret;
605 }
#define C5
F77_RET_T const F77_INT const F77_INT const F77_INT const F77_DBLE const F77_DBLE F77_INT F77_DBLE * V
#define C7
static void poisson_cdf_lookup(double lambda, double *p, size_t n)
Definition: randpoisson.cc:285
for large enough k
Definition: lu.cc:617
OCTAVE_EXPORT octave_value_list or N dimensional array whose elements are all equal to the base of natural logarithms The constant ex $e satisfies the equation log(e)
#define RUNI
Definition: randpoisson.cc:49
std::complex< T > ceil(const std::complex< T > &x)
Definition: lo-mappers.h:112
#define TABLESIZE
std::complex< T > floor(const std::complex< T > &x)
Definition: lo-mappers.h:139
static double flogfak(double k)
Definition: randpoisson.cc:63
#define INFINITE
Definition: randpoisson.cc:48
static double xlgamma(double x)
Definition: randpoisson.cc:54
u
Definition: lu.cc:138
OCTAVE_EXPORT octave_value_list return the number of command line arguments passed to Octave If called with the optional argument the function t
Definition: ov-usr-fcn.cc:997
static void poisson_rejection_float(double lambda, float *p, size_t n)
Definition: randpoisson.cc:430
#define C0
#define RNOR
Definition: randpoisson.cc:50
double lgamma(double x)
Definition: lo-specfun.h:377
double oct_randp(double L)
Definition: randpoisson.cc:497
static double pprsc(double my)
Definition: randpoisson.cc:136
static void poisson_rejection(double lambda, double *p, size_t n)
Definition: randpoisson.cc:404
static void poisson_cdf_lookup_float(double lambda, float *p, size_t n)
Definition: randpoisson.cc:358
void oct_fill_float_randp(float FL, octave_idx_type n, float *p)
Definition: randpoisson.cc:536
#define LGAMMA
Definition: randpoisson.cc:51
OCTAVE_EXPORT octave_value_list or N dimensional array whose elements are all equal to the IEEE symbol NaN(Not a Number). NaN is the result of operations which do not produce a well defined 0 result. Common operations which produce a NaN are arithmetic with infinity ex($\infty - \infty$)
p
Definition: lu.cc:138
#define C3
the element is set to zero In other the statement xample y
Definition: data.cc:5264
for i
Definition: data.cc:5264
static double f(double k, double l_nu, double c_pm)
Definition: randpoisson.cc:130
float oct_float_randp(float FL)
Definition: randpoisson.cc:569
#define C1
F77_RET_T const F77_REAL const F77_REAL F77_REAL &F77_RET_T const F77_DBLE const F77_DBLE F77_DBLE &F77_RET_T const F77_DBLE F77_DBLE &F77_RET_T const F77_REAL F77_REAL &F77_RET_T const F77_DBLE * x
void oct_fill_randp(double L, octave_idx_type n, double *p)
Definition: randpoisson.cc:465