View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.special;
18  
19  import org.apache.commons.math.MathException;
20  import org.apache.commons.math.MaxIterationsExceededException;
21  import org.apache.commons.math.util.ContinuedFraction;
22  
23  /**
24   * This is a utility class that provides computation methods related to the
25   * Gamma family of functions.
26   *
27   * @version $Revision: 780975 $ $Date: 2009-06-02 05:05:37 -0400 (Tue, 02 Jun 2009) $
28   */
29  public class Gamma {
30      
31      /** 
32       * <a href="http://en.wikipedia.org/wiki/Euler-Mascheroni_constant">Euler-Mascheroni constant</a>
33       * @since 2.0
34       */
35      public static final double GAMMA = 0.577215664901532860606512090082;
36  
37      /** Maximum allowed numerical error. */
38      private static final double DEFAULT_EPSILON = 10e-15;
39  
40      /** Lanczos coefficients */
41      private static final double[] lanczos =
42      {
43          0.99999999999999709182,
44          57.156235665862923517,
45          -59.597960355475491248,
46          14.136097974741747174,
47          -0.49191381609762019978,
48          .33994649984811888699e-4,
49          .46523628927048575665e-4,
50          -.98374475304879564677e-4,
51          .15808870322491248884e-3,
52          -.21026444172410488319e-3,
53          .21743961811521264320e-3,
54          -.16431810653676389022e-3,
55          .84418223983852743293e-4,
56          -.26190838401581408670e-4,
57          .36899182659531622704e-5,
58      };
59  
60      /** Avoid repeated computation of log of 2 PI in logGamma */
61      private static final double HALF_LOG_2_PI = 0.5 * Math.log(2.0 * Math.PI);
62  
63  
64      /**
65       * Default constructor.  Prohibit instantiation.
66       */
67      private Gamma() {
68          super();
69      }
70  
71      /**
72       * Returns the natural logarithm of the gamma function &#915;(x).
73       *
74       * The implementation of this method is based on:
75       * <ul>
76       * <li><a href="http://mathworld.wolfram.com/GammaFunction.html">
77       * Gamma Function</a>, equation (28).</li>
78       * <li><a href="http://mathworld.wolfram.com/LanczosApproximation.html">
79       * Lanczos Approximation</a>, equations (1) through (5).</li>
80       * <li><a href="http://my.fit.edu/~gabdo/gamma.txt">Paul Godfrey, A note on
81       * the computation of the convergent Lanczos complex Gamma approximation
82       * </a></li>
83       * </ul>
84       * 
85       * @param x the value.
86       * @return log(&#915;(x))
87       */
88      public static double logGamma(double x) {
89          double ret;
90  
91          if (Double.isNaN(x) || (x <= 0.0)) {
92              ret = Double.NaN;
93          } else {
94              double g = 607.0 / 128.0;
95              
96              double sum = 0.0;
97              for (int i = lanczos.length - 1; i > 0; --i) {
98                  sum = sum + (lanczos[i] / (x + i));
99              }
100             sum = sum + lanczos[0];
101 
102             double tmp = x + g + .5;
103             ret = ((x + .5) * Math.log(tmp)) - tmp +
104                 HALF_LOG_2_PI + Math.log(sum / x);
105         }
106 
107         return ret;
108     }
109 
110     /**
111      * Returns the regularized gamma function P(a, x).
112      * 
113      * @param a the a parameter.
114      * @param x the value.
115      * @return the regularized gamma function P(a, x)
116      * @throws MathException if the algorithm fails to converge.
117      */
118     public static double regularizedGammaP(double a, double x)
119         throws MathException
120     {
121         return regularizedGammaP(a, x, DEFAULT_EPSILON, Integer.MAX_VALUE);
122     }
123         
124         
125     /**
126      * Returns the regularized gamma function P(a, x).
127      * 
128      * The implementation of this method is based on:
129      * <ul>
130      * <li>
131      * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
132      * Regularized Gamma Function</a>, equation (1).</li>
133      * <li>
134      * <a href="http://mathworld.wolfram.com/IncompleteGammaFunction.html">
135      * Incomplete Gamma Function</a>, equation (4).</li>
136      * <li>
137      * <a href="http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheFirstKind.html">
138      * Confluent Hypergeometric Function of the First Kind</a>, equation (1).
139      * </li>
140      * </ul>
141      * 
142      * @param a the a parameter.
143      * @param x the value.
144      * @param epsilon When the absolute value of the nth item in the
145      *                series is less than epsilon the approximation ceases
146      *                to calculate further elements in the series.
147      * @param maxIterations Maximum number of "iterations" to complete. 
148      * @return the regularized gamma function P(a, x)
149      * @throws MathException if the algorithm fails to converge.
150      */
151     public static double regularizedGammaP(double a, 
152                                            double x, 
153                                            double epsilon, 
154                                            int maxIterations) 
155         throws MathException
156     {
157         double ret;
158 
159         if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
160             ret = Double.NaN;
161         } else if (x == 0.0) {
162             ret = 0.0;
163         } else if (a >= 1.0 && x > a) {
164             // use regularizedGammaQ because it should converge faster in this
165             // case.
166             ret = 1.0 - regularizedGammaQ(a, x, epsilon, maxIterations);
167         } else {
168             // calculate series
169             double n = 0.0; // current element index
170             double an = 1.0 / a; // n-th element in the series
171             double sum = an; // partial sum
172             while (Math.abs(an) > epsilon && n < maxIterations) {
173                 // compute next element in the series
174                 n = n + 1.0;
175                 an = an * (x / (a + n));
176 
177                 // update partial sum
178                 sum = sum + an;
179             }
180             if (n >= maxIterations) {
181                 throw new MaxIterationsExceededException(maxIterations);
182             } else {
183                 ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * sum;
184             }
185         }
186 
187         return ret;
188     }
189     
190     /**
191      * Returns the regularized gamma function Q(a, x) = 1 - P(a, x).
192      * 
193      * @param a the a parameter.
194      * @param x the value.
195      * @return the regularized gamma function Q(a, x)
196      * @throws MathException if the algorithm fails to converge.
197      */
198     public static double regularizedGammaQ(double a, double x)
199         throws MathException
200     {
201         return regularizedGammaQ(a, x, DEFAULT_EPSILON, Integer.MAX_VALUE);
202     }
203     
204     /**
205      * Returns the regularized gamma function Q(a, x) = 1 - P(a, x).
206      * 
207      * The implementation of this method is based on:
208      * <ul>
209      * <li>
210      * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
211      * Regularized Gamma Function</a>, equation (1).</li>
212      * <li>
213      * <a href="    http://functions.wolfram.com/GammaBetaErf/GammaRegularized/10/0003/">
214      * Regularized incomplete gamma function: Continued fraction representations  (formula 06.08.10.0003)</a></li>
215      * </ul>
216      * 
217      * @param a the a parameter.
218      * @param x the value.
219      * @param epsilon When the absolute value of the nth item in the
220      *                series is less than epsilon the approximation ceases
221      *                to calculate further elements in the series.
222      * @param maxIterations Maximum number of "iterations" to complete. 
223      * @return the regularized gamma function P(a, x)
224      * @throws MathException if the algorithm fails to converge.
225      */
226     public static double regularizedGammaQ(final double a, 
227                                            double x, 
228                                            double epsilon, 
229                                            int maxIterations) 
230         throws MathException
231     {
232         double ret;
233 
234         if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
235             ret = Double.NaN;
236         } else if (x == 0.0) {
237             ret = 1.0;
238         } else if (x < a || a < 1.0) {
239             // use regularizedGammaP because it should converge faster in this
240             // case.
241             ret = 1.0 - regularizedGammaP(a, x, epsilon, maxIterations);
242         } else {
243             // create continued fraction
244             ContinuedFraction cf = new ContinuedFraction() {
245 
246                 @Override
247                 protected double getA(int n, double x) {
248                     return ((2.0 * n) + 1.0) - a + x;
249                 }
250 
251                 @Override
252                 protected double getB(int n, double x) {
253                     return n * (a - n);
254                 }
255             };
256             
257             ret = 1.0 / cf.evaluate(x, epsilon, maxIterations);
258             ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * ret;
259         }
260 
261         return ret;
262     }
263 
264 
265     // limits for switching algorithm in digamma
266     /** C limit */
267      private static final double C_LIMIT = 49;
268      /** S limit */
269      private static final double S_LIMIT = 1e-5;
270 
271     /**
272      * <p>Computes the digamma function of x.</p>
273      * 
274      * <p>This is an independently written implementation of the algorithm described in
275      * Jose Bernardo, Algorithm AS 103: Psi (Digamma) Function, Applied Statistics, 1976.</p>
276      * 
277      * <p>Some of the constants have been changed to increase accuracy at the moderate expense
278      * of run-time.  The result should be accurate to within 10^-8 absolute tolerance for
279      * x >= 10^-5 and within 10^-8 relative tolerance for x > 0.</p>
280      * 
281      * <p>Performance for large negative values of x will be quite expensive (proportional to
282      * |x|).  Accuracy for negative values of x should be about 10^-8 absolute for results
283      * less than 10^5 and 10^-8 relative for results larger than that.</p>
284      * 
285      * @param x  the argument
286      * @return   digamma(x) to within 10-8 relative or absolute error whichever is smaller
287      * @see <a href="http://en.wikipedia.org/wiki/Digamma_function"> Digamma at wikipedia </a>
288      * @see <a href="http://www.uv.es/~bernardo/1976AppStatist.pdf"> Bernardo's original article </a>
289      * @since 2.0
290      */
291     public static double digamma(double x) {
292         if (x > 0 && x <= S_LIMIT) {
293             // use method 5 from Bernardo AS103
294             // accurate to O(x)
295             return -GAMMA - 1 / x;
296         }
297 
298         if (x >= C_LIMIT) {
299             // use method 4 (accurate to O(1/x^8)
300             double inv = 1 / (x * x);
301             //            1       1        1         1
302             // log(x) -  --- - ------ + ------- - -------
303             //           2 x   12 x^2   120 x^4   252 x^6
304             return Math.log(x) - 0.5 / x - inv * ((1.0 / 12) + inv * (1.0 / 120 - inv / 252));
305         }
306 
307         return digamma(x + 1) - 1 / x;
308     }
309 
310     /**
311      * <p>Computes the trigamma function of x.  This function is derived by taking the derivative of
312      * the implementation of digamma.</p>
313      * 
314      * @param x  the argument
315      * @return   trigamma(x) to within 10-8 relative or absolute error whichever is smaller
316      * @see <a href="http://en.wikipedia.org/wiki/Trigamma_function"> Trigamma at wikipedia </a>
317      * @see Gamma#digamma(double)
318      * @since 2.0
319      */
320     public static double trigamma(double x) {
321         if (x > 0 && x <= S_LIMIT) {
322             return 1 / (x * x);
323         }
324 
325         if (x >= C_LIMIT) {
326             double inv = 1 / (x * x);
327             //  1    1      1       1       1
328             //  - + ---- + ---- - ----- + -----
329             //  x      2      3       5       7
330             //      2 x    6 x    30 x    42 x
331             return 1 / x + inv / 2 + inv / x * (1.0 / 6 - inv * (1.0 / 30 + inv / 42));
332         }
333 
334         return trigamma(x + 1) + 1 / (x * x);
335     }
336 }