001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math.special;
018    
019    import org.apache.commons.math.MathException;
020    import org.apache.commons.math.MaxIterationsExceededException;
021    import org.apache.commons.math.util.ContinuedFraction;
022    
023    /**
024     * This is a utility class that provides computation methods related to the
025     * Gamma family of functions.
026     *
027     * @version $Revision: 920558 $ $Date: 2010-03-08 17:57:32 -0500 (Mon, 08 Mar 2010) $
028     */
029    public class Gamma {
030    
031        /**
032         * <a href="http://en.wikipedia.org/wiki/Euler-Mascheroni_constant">Euler-Mascheroni constant</a>
033         * @since 2.0
034         */
035        public static final double GAMMA = 0.577215664901532860606512090082;
036    
037        /** Maximum allowed numerical error. */
038        private static final double DEFAULT_EPSILON = 10e-15;
039    
040        /** Lanczos coefficients */
041        private static final double[] LANCZOS =
042        {
043            0.99999999999999709182,
044            57.156235665862923517,
045            -59.597960355475491248,
046            14.136097974741747174,
047            -0.49191381609762019978,
048            .33994649984811888699e-4,
049            .46523628927048575665e-4,
050            -.98374475304879564677e-4,
051            .15808870322491248884e-3,
052            -.21026444172410488319e-3,
053            .21743961811521264320e-3,
054            -.16431810653676389022e-3,
055            .84418223983852743293e-4,
056            -.26190838401581408670e-4,
057            .36899182659531622704e-5,
058        };
059    
060        /** Avoid repeated computation of log of 2 PI in logGamma */
061        private static final double HALF_LOG_2_PI = 0.5 * Math.log(2.0 * Math.PI);
062    
063        // limits for switching algorithm in digamma
064        /** C limit. */
065        private static final double C_LIMIT = 49;
066    
067        /** S limit. */
068        private static final double S_LIMIT = 1e-5;
069    
070        /**
071         * Default constructor.  Prohibit instantiation.
072         */
073        private Gamma() {
074            super();
075        }
076    
077        /**
078         * Returns the natural logarithm of the gamma function &#915;(x).
079         *
080         * The implementation of this method is based on:
081         * <ul>
082         * <li><a href="http://mathworld.wolfram.com/GammaFunction.html">
083         * Gamma Function</a>, equation (28).</li>
084         * <li><a href="http://mathworld.wolfram.com/LanczosApproximation.html">
085         * Lanczos Approximation</a>, equations (1) through (5).</li>
086         * <li><a href="http://my.fit.edu/~gabdo/gamma.txt">Paul Godfrey, A note on
087         * the computation of the convergent Lanczos complex Gamma approximation
088         * </a></li>
089         * </ul>
090         *
091         * @param x the value.
092         * @return log(&#915;(x))
093         */
094        public static double logGamma(double x) {
095            double ret;
096    
097            if (Double.isNaN(x) || (x <= 0.0)) {
098                ret = Double.NaN;
099            } else {
100                double g = 607.0 / 128.0;
101    
102                double sum = 0.0;
103                for (int i = LANCZOS.length - 1; i > 0; --i) {
104                    sum = sum + (LANCZOS[i] / (x + i));
105                }
106                sum = sum + LANCZOS[0];
107    
108                double tmp = x + g + .5;
109                ret = ((x + .5) * Math.log(tmp)) - tmp +
110                    HALF_LOG_2_PI + Math.log(sum / x);
111            }
112    
113            return ret;
114        }
115    
116        /**
117         * Returns the regularized gamma function P(a, x).
118         *
119         * @param a the a parameter.
120         * @param x the value.
121         * @return the regularized gamma function P(a, x)
122         * @throws MathException if the algorithm fails to converge.
123         */
124        public static double regularizedGammaP(double a, double x)
125            throws MathException
126        {
127            return regularizedGammaP(a, x, DEFAULT_EPSILON, Integer.MAX_VALUE);
128        }
129    
130    
131        /**
132         * Returns the regularized gamma function P(a, x).
133         *
134         * The implementation of this method is based on:
135         * <ul>
136         * <li>
137         * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
138         * Regularized Gamma Function</a>, equation (1).</li>
139         * <li>
140         * <a href="http://mathworld.wolfram.com/IncompleteGammaFunction.html">
141         * Incomplete Gamma Function</a>, equation (4).</li>
142         * <li>
143         * <a href="http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheFirstKind.html">
144         * Confluent Hypergeometric Function of the First Kind</a>, equation (1).
145         * </li>
146         * </ul>
147         *
148         * @param a the a parameter.
149         * @param x the value.
150         * @param epsilon When the absolute value of the nth item in the
151         *                series is less than epsilon the approximation ceases
152         *                to calculate further elements in the series.
153         * @param maxIterations Maximum number of "iterations" to complete.
154         * @return the regularized gamma function P(a, x)
155         * @throws MathException if the algorithm fails to converge.
156         */
157        public static double regularizedGammaP(double a,
158                                               double x,
159                                               double epsilon,
160                                               int maxIterations)
161            throws MathException
162        {
163            double ret;
164    
165            if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
166                ret = Double.NaN;
167            } else if (x == 0.0) {
168                ret = 0.0;
169            } else if (x >= a + 1) {
170                // use regularizedGammaQ because it should converge faster in this
171                // case.
172                ret = 1.0 - regularizedGammaQ(a, x, epsilon, maxIterations);
173            } else {
174                // calculate series
175                double n = 0.0; // current element index
176                double an = 1.0 / a; // n-th element in the series
177                double sum = an; // partial sum
178                while (Math.abs(an/sum) > epsilon && n < maxIterations && sum < Double.POSITIVE_INFINITY) {
179                    // compute next element in the series
180                    n = n + 1.0;
181                    an = an * (x / (a + n));
182    
183                    // update partial sum
184                    sum = sum + an;
185                }
186                if (n >= maxIterations) {
187                    throw new MaxIterationsExceededException(maxIterations);
188                } else if (Double.isInfinite(sum)) {
189                    ret = 1.0;
190                } else {
191                    ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * sum;
192                }
193            }
194    
195            return ret;
196        }
197    
198        /**
199         * Returns the regularized gamma function Q(a, x) = 1 - P(a, x).
200         *
201         * @param a the a parameter.
202         * @param x the value.
203         * @return the regularized gamma function Q(a, x)
204         * @throws MathException if the algorithm fails to converge.
205         */
206        public static double regularizedGammaQ(double a, double x)
207            throws MathException
208        {
209            return regularizedGammaQ(a, x, DEFAULT_EPSILON, Integer.MAX_VALUE);
210        }
211    
212        /**
213         * Returns the regularized gamma function Q(a, x) = 1 - P(a, x).
214         *
215         * The implementation of this method is based on:
216         * <ul>
217         * <li>
218         * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
219         * Regularized Gamma Function</a>, equation (1).</li>
220         * <li>
221         * <a href="http://functions.wolfram.com/GammaBetaErf/GammaRegularized/10/0003/">
222         * Regularized incomplete gamma function: Continued fraction representations  (formula 06.08.10.0003)</a></li>
223         * </ul>
224         *
225         * @param a the a parameter.
226         * @param x the value.
227         * @param epsilon When the absolute value of the nth item in the
228         *                series is less than epsilon the approximation ceases
229         *                to calculate further elements in the series.
230         * @param maxIterations Maximum number of "iterations" to complete.
231         * @return the regularized gamma function P(a, x)
232         * @throws MathException if the algorithm fails to converge.
233         */
234        public static double regularizedGammaQ(final double a,
235                                               double x,
236                                               double epsilon,
237                                               int maxIterations)
238            throws MathException
239        {
240            double ret;
241    
242            if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
243                ret = Double.NaN;
244            } else if (x == 0.0) {
245                ret = 1.0;
246            } else if (x < a + 1.0) {
247                // use regularizedGammaP because it should converge faster in this
248                // case.
249                ret = 1.0 - regularizedGammaP(a, x, epsilon, maxIterations);
250            } else {
251                // create continued fraction
252                ContinuedFraction cf = new ContinuedFraction() {
253    
254                    @Override
255                    protected double getA(int n, double x) {
256                        return ((2.0 * n) + 1.0) - a + x;
257                    }
258    
259                    @Override
260                    protected double getB(int n, double x) {
261                        return n * (a - n);
262                    }
263                };
264    
265                ret = 1.0 / cf.evaluate(x, epsilon, maxIterations);
266                ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * ret;
267            }
268    
269            return ret;
270        }
271    
272    
273        /**
274         * <p>Computes the digamma function of x.</p>
275         *
276         * <p>This is an independently written implementation of the algorithm described in
277         * Jose Bernardo, Algorithm AS 103: Psi (Digamma) Function, Applied Statistics, 1976.</p>
278         *
279         * <p>Some of the constants have been changed to increase accuracy at the moderate expense
280         * of run-time.  The result should be accurate to within 10^-8 absolute tolerance for
281         * x >= 10^-5 and within 10^-8 relative tolerance for x > 0.</p>
282         *
283         * <p>Performance for large negative values of x will be quite expensive (proportional to
284         * |x|).  Accuracy for negative values of x should be about 10^-8 absolute for results
285         * less than 10^5 and 10^-8 relative for results larger than that.</p>
286         *
287         * @param x  the argument
288         * @return   digamma(x) to within 10-8 relative or absolute error whichever is smaller
289         * @see <a href="http://en.wikipedia.org/wiki/Digamma_function"> Digamma at wikipedia </a>
290         * @see <a href="http://www.uv.es/~bernardo/1976AppStatist.pdf"> Bernardo's original article </a>
291         * @since 2.0
292         */
293        public static double digamma(double x) {
294            if (x > 0 && x <= S_LIMIT) {
295                // use method 5 from Bernardo AS103
296                // accurate to O(x)
297                return -GAMMA - 1 / x;
298            }
299    
300            if (x >= C_LIMIT) {
301                // use method 4 (accurate to O(1/x^8)
302                double inv = 1 / (x * x);
303                //            1       1        1         1
304                // log(x) -  --- - ------ + ------- - -------
305                //           2 x   12 x^2   120 x^4   252 x^6
306                return Math.log(x) - 0.5 / x - inv * ((1.0 / 12) + inv * (1.0 / 120 - inv / 252));
307            }
308    
309            return digamma(x + 1) - 1 / x;
310        }
311    
312        /**
313         * <p>Computes the trigamma function of x.  This function is derived by taking the derivative of
314         * the implementation of digamma.</p>
315         *
316         * @param x  the argument
317         * @return   trigamma(x) to within 10-8 relative or absolute error whichever is smaller
318         * @see <a href="http://en.wikipedia.org/wiki/Trigamma_function"> Trigamma at wikipedia </a>
319         * @see Gamma#digamma(double)
320         * @since 2.0
321         */
322        public static double trigamma(double x) {
323            if (x > 0 && x <= S_LIMIT) {
324                return 1 / (x * x);
325            }
326    
327            if (x >= C_LIMIT) {
328                double inv = 1 / (x * x);
329                //  1    1      1       1       1
330                //  - + ---- + ---- - ----- + -----
331                //  x      2      3       5       7
332                //      2 x    6 x    30 x    42 x
333                return 1 / x + inv / 2 + inv / x * (1.0 / 6 - inv * (1.0 / 30 + inv / 42));
334            }
335    
336            return trigamma(x + 1) + 1 / (x * x);
337        }
338    }