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