htswanalysis/MACS/lib/gsl/gsl-1.11/randist/binomial.c

   1 /* randist/binomial.c
   2  *
   3  * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 James Theiler, Brian Gough
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  */
  19
  20 #include <config.h>
  21 #include <math.h>
  22 #include <gsl/gsl_sys.h>
  23 #include <gsl/gsl_rng.h>
  24 #include <gsl/gsl_randist.h>
  25 #include <gsl/gsl_sf_gamma.h>
  26
  27 /* The binomial distribution has the form,
  28
  29    prob(k) =  n!/(k!(n-k)!) *  p^k (1-p)^(n-k) for k = 0, 1, ..., n
  30
  31    This is the algorithm from Knuth */
  32
  33 /* Default binomial generator is now in binomial_tpe.c */
  34
  35 unsigned int
  36 gsl_ran_binomial_knuth (const gsl_rng * r, double p, unsigned int n)
  37 {
  38   unsigned int i, a, b, k = 0;
  39
  40   while (n > 10)        /* This parameter is tunable */
  41     {
  42       double X;
  43       a = 1 + (n / 2);
  44       b = 1 + n - a;
  45
  46       X = gsl_ran_beta (r, (double) a, (double) b);
  47
  48       if (X >= p)
  49         {
  50           n = a - 1;
  51           p /= X;
  52         }
  53       else
  54         {
  55           k += a;
  56           n = b - 1;
  57           p = (p - X) / (1 - X);
  58         }
  59     }
  60
  61   for (i = 0; i < n; i++)
  62     {
  63       double u = gsl_rng_uniform (r);
  64       if (u < p)
  65         k++;
  66     }
  67
  68   return k;
  69 }
  70
  71 double
  72 gsl_ran_binomial_pdf (const unsigned int k, const double p,
  73                       const unsigned int n)
  74 {
  75   if (k > n)
  76     {
  77       return 0;
  78     }
  79   else
  80     {
  81       double P;
  82
  83       if (p == 0)
  84         {
  85           P = (k == 0) ? 1 : 0;
  86         }
  87       else if (p == 1)
  88         {
  89           P = (k == n) ? 1 : 0;
  90         }
  91       else
  92         {
  93           double ln_Cnk = gsl_sf_lnchoose (n, k);
  94           P = ln_Cnk + k * log (p) + (n - k) * log1p (-p);
  95           P = exp (P);
  96         }
  97
  98       return P;
  99     }
 100 }