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 Γ(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(Γ(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 }