code: /*
   * Copyright 2012-2018 Chronicle Map Contributors
   * Copyright 2001-2015 The Apache Software Foundation
   * Copyright 2010-2012 CS Systèmes d'Information
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package net.openhft.chronicle.hash.impl.util.math;
  
  /**
   * <p>
   * This is a utility class that provides computation methods related to the
   * &Gamma; (Gamma) family of functions.
   * </p>
   * <p>
   * Implementation of {@link #invGamma1pm1(double)} and
   * {@link #logGamma1p(double)} is based on the algorithms described in
   * <ul>
   * <li><a href="http://dx.doi.org/10.1145/22721.23109">Didonato and Morris
   * (1986)</a>, <em>Computation of the Incomplete Gamma Function Ratios and
   * their Inverse</em>, TOMS 12(4), 377-393,</li>
   * <li><a href="http://dx.doi.org/10.1145/131766.131776">Didonato and Morris
   * (1992)</a>, <em>Algorithm 708: Significant Digit Computation of the
   * Incomplete Beta Function Ratios</em>, TOMS 18(3), 360-373,</li>
   * </ul>
   * and implemented in the
   * <a href="http://www.dtic.mil/docs/citations/ADA476840">NSWC Library of Mathematical Functions</a>,
   * available
   * <a href="http://www.ualberta.ca/CNS/RESEARCH/Software/NumericalNSWC/site.html">here</a>.
   * This library is "approved for public release", and the
   * <a href="http://www.dtic.mil/dtic/pdf/announcements/CopyrightGuidance.pdf">Copyright guidance</a>
   * indicates that unless otherwise stated in the code, all FORTRAN functions in
   * this library are license free. Since no such notice appears in the code these
   * functions can safely be ported to Commons-Math.
   * </p>
   */
  class Gamma {
  
      /**
       * The value of the {@code g} constant in the Lanczos approximation, see
       * {@link #lanczos(double)}.
       *
       * @since 3.1
       */
      public static final double LANCZOS_G = 607.0 / 128.0;
  
      /**
       * Lanczos coefficients
       */
      private static final double[] LANCZOS = {
              0.99999999999999709182,
              57.156235665862923517,
              -59.597960355475491248,
              14.136097974741747174,
              -0.49191381609762019978,
              .33994649984811888699e-4,
              .46523628927048575665e-4,
              -.98374475304879564677e-4,
              .15808870322491248884e-3,
              -.21026444172410488319e-3,
              .21743961811521264320e-3,
              -.16431810653676389022e-3,
              .84418223983852743293e-4,
              -.26190838401581408670e-4,
              .36899182659531622704e-5,
      };
  
      /**
       * Avoid repeated computation of log of 2 PI in logGamma
       */
      private static final double HALF_LOG_2_PI = 0.5 * Math.log(2.0 * Math.PI);
  
      /*
       * Constants for the computation of double invGamma1pm1(double).
       * Copied from DGAM1 in the NSWC library.
       */
  
      /**
       * The constant {@code A0} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_A0 = .611609510448141581788E-08;
  
      /**
       * The constant {@code A1} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_A1 = .624730830116465516210E-08;
  
      /**
       * The constant {@code B1} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B1 = .203610414066806987300E+00;
  
      /**
       * The constant {@code B2} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B2 = .266205348428949217746E-01;
  
      /**
       * The constant {@code B3} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B3 = .493944979382446875238E-03;
  
      /**
       * The constant {@code B4} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B4 = -.851419432440314906588E-05;
  
      /**
       * The constant {@code B5} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B5 = -.643045481779353022248E-05;
  
      /**
       * The constant {@code B6} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B6 = .992641840672773722196E-06;
  
      /**
       * The constant {@code B7} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B7 = -.607761895722825260739E-07;
  
      /**
       * The constant {@code B8} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_B8 = .195755836614639731882E-09;
  
      /**
       * The constant {@code P0} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P0 = .6116095104481415817861E-08;
  
      /**
       * The constant {@code P1} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P1 = .6871674113067198736152E-08;
  
      /**
       * The constant {@code P2} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P2 = .6820161668496170657918E-09;
  
      /**
       * The constant {@code P3} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P3 = .4686843322948848031080E-10;
  
      /**
       * The constant {@code P4} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P4 = .1572833027710446286995E-11;
  
      /**
       * The constant {@code P5} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P5 = -.1249441572276366213222E-12;
  
      /**
       * The constant {@code P6} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_P6 = .4343529937408594255178E-14;
  
      /**
       * The constant {@code Q1} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_Q1 = .3056961078365221025009E+00;
  
      /**
       * The constant {@code Q2} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_Q2 = .5464213086042296536016E-01;
  
      /**
       * The constant {@code Q3} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_Q3 = .4956830093825887312020E-02;
  
      /**
       * The constant {@code Q4} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_Q4 = .2692369466186361192876E-03;
  
      /**
       * The constant {@code C} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C = -.422784335098467139393487909917598E+00;
  
      /**
       * The constant {@code C0} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C0 = .577215664901532860606512090082402E+00;
  
      /**
       * The constant {@code C1} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C1 = -.655878071520253881077019515145390E+00;
  
      /**
       * The constant {@code C2} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C2 = -.420026350340952355290039348754298E-01;
  
      /**
       * The constant {@code C3} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C3 = .166538611382291489501700795102105E+00;
  
      /**
       * The constant {@code C4} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C4 = -.421977345555443367482083012891874E-01;
  
      /**
       * The constant {@code C5} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C5 = -.962197152787697356211492167234820E-02;
  
      /**
       * The constant {@code C6} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C6 = .721894324666309954239501034044657E-02;
  
      /**
       * The constant {@code C7} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C7 = -.116516759185906511211397108401839E-02;
  
      /**
       * The constant {@code C8} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C8 = -.215241674114950972815729963053648E-03;
  
      /**
       * The constant {@code C9} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C9 = .128050282388116186153198626328164E-03;
  
      /**
       * The constant {@code C10} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C10 = -.201348547807882386556893914210218E-04;
  
      /**
       * The constant {@code C11} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C11 = -.125049348214267065734535947383309E-05;
  
      /**
       * The constant {@code C12} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C12 = .113302723198169588237412962033074E-05;
  
      /**
       * The constant {@code C13} defined in {@code DGAM1}.
       */
      private static final double INV_GAMMA1P_M1_C13 = -.205633841697760710345015413002057E-06;
  
      /**
       * Default constructor.  Prohibit instantiation.
       */
      private Gamma() {
      }
  
      /**
       * <p>
       * Returns the value of log&nbsp;&Gamma;(x) for x&nbsp;&gt;&nbsp;0.
       * </p>
       * <p>
       * For x &le; 8, the implementation is based on the double precision
       * implementation in the <em>NSWC Library of Mathematics Subroutines</em>,
       * {@code DGAMLN}. For x &gt; 8, the implementation is based on
       * </p>
       * <ul>
       * <li><a href="http://mathworld.wolfram.com/GammaFunction.html">Gamma
       * Function</a>, equation (28).</li>
       * <li><a href="http://mathworld.wolfram.com/LanczosApproximation.html">
       * Lanczos Approximation</a>, equations (1) through (5).</li>
       * <li><a href="http://my.fit.edu/~gabdo/gamma.txt">Paul Godfrey, A note on
       * the computation of the convergent Lanczos complex Gamma
       * approximation</a></li>
       * </ul>
       *
       * @param x Argument.
       * @return the value of {@code log(Gamma(x))}, {@code Double.NaN} if
       * {@code x <= 0.0}.
       */
      public static double logGamma(double x) {
          double ret;
  
          if (Double.isNaN(x) || (x <= 0.0)) {
              ret = Double.NaN;
          } else if (x < 0.5) {
              return logGamma1p(x) - Math.log(x);
          } else if (x <= 2.5) {
              return logGamma1p((x - 0.5) - 0.5);
          } else if (x <= 8.0) {
              final int n = (int) Math.floor(x - 1.5);
              double prod = 1.0;
              for (int i = 1; i <= n; i++) {
                  prod *= x - i;
              }
              return logGamma1p(x - (n + 1)) + Math.log(prod);
          } else {
              double sum = lanczos(x);
              double tmp = x + LANCZOS_G + .5;
              ret = ((x + .5) * Math.log(tmp)) - tmp +
                      HALF_LOG_2_PI + Math.log(sum / x);
          }
  
          return ret;
      }
  
      /**
       * Returns the regularized gamma function P(a, x).
       * <p>
       * The implementation of this method is based on:
       * <ul>
       * <li>
       * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
       * Regularized Gamma Function</a>, equation (1)
       * </li>
       * <li>
       * <a href="http://mathworld.wolfram.com/IncompleteGammaFunction.html">
       * Incomplete Gamma Function</a>, equation (4).
       * </li>
       * <li>
       * <a href="http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheFirstKind.html">
       * Confluent Hypergeometric Function of the First Kind</a>, equation (1).
       * </li>
       * </ul>
       *
       * @param a             the a parameter.
       * @param x             the value.
       * @param epsilon       When the absolute value of the nth item in the
       *                      series is less than epsilon the approximation ceases to calculate
       *                      further elements in the series.
       * @param maxIterations Maximum number of "iterations" to complete.
       * @return the regularized gamma function P(a, x)
       * @throws IllegalStateException if the algorithm fails to converge.
       */
      public static double regularizedGammaP(double a,
                                             double x,
                                             double epsilon,
                                             int maxIterations) {
          double ret;
  
          if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
              ret = Double.NaN;
          } else if (x == 0.0) {
              ret = 0.0;
          } else if (x >= a + 1) {
              // use regularizedGammaQ because it should converge faster in this
              // case.
              ret = 1.0 - regularizedGammaQ(a, x, epsilon, maxIterations);
          } else {
              // calculate series
              double n = 0.0; // current element index
              double an = 1.0 / a; // n-th element in the series
              double sum = an; // partial sum
              while (Math.abs(an / sum) > epsilon &&
                      n < maxIterations &&
                      sum < Double.POSITIVE_INFINITY) {
                  // compute next element in the series
                  n += 1.0;
                  an *= x / (a + n);
  
                  // update partial sum
                  sum += an;
              }
              if (n >= maxIterations) {
                  throw new IllegalStateException("max count exceeded: " + maxIterations);
              } else if (Double.isInfinite(sum)) {
                  ret = 1.0;
              } else {
                  ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * sum;
              }
          }
  
          return ret;
      }
  
      /**
       * Returns the regularized gamma function Q(a, x) = 1 - P(a, x).
       * <p>
       * The implementation of this method is based on:
       * <ul>
       * <li>
       * <a href="http://mathworld.wolfram.com/RegularizedGammaFunction.html">
       * Regularized Gamma Function</a>, equation (1).
       * </li>
       * <li>
       * <a href="http://functions.wolfram.com/GammaBetaErf/GammaRegularized/10/0003/">
       * Regularized incomplete gamma function: Continued fraction representations
       * (formula 06.08.10.0003)</a>
       * </li>
       * </ul>
       *
       * @param a             the a parameter.
       * @param x             the value.
       * @param epsilon       When the absolute value of the nth item in the
       *                      series is less than epsilon the approximation ceases to calculate
       *                      further elements in the series.
       * @param maxIterations Maximum number of "iterations" to complete.
       * @return the regularized gamma function P(a, x)
       * @throws IllegalStateException if the algorithm fails to converge.
       */
      public static double regularizedGammaQ(final double a,
                                             double x,
                                             double epsilon,
                                             int maxIterations) {
          double ret;
  
          if (Double.isNaN(a) || Double.isNaN(x) || (a <= 0.0) || (x < 0.0)) {
              ret = Double.NaN;
          } else if (x == 0.0) {
              ret = 1.0;
          } else if (x < a + 1.0) {
              // use regularizedGammaP because it should converge faster in this
              // case.
              ret = 1.0 - regularizedGammaP(a, x, epsilon, maxIterations);
          } else {
              // create continued fraction
              ContinuedFraction cf = new ContinuedFraction() {
  
                  @Override
                  protected double getA(int n, double x) {
                      return ((2.0 * n) + 1.0) - a + x;
                  }
  
                  @Override
                  protected double getB(int n, double x) {
                      return n * (a - n);
                  }
              };
  
              ret = 1.0 / cf.evaluate(x, epsilon, maxIterations);
              ret = Math.exp(-x + (a * Math.log(x)) - logGamma(a)) * ret;
          }
  
          return ret;
      }
  
      /**
       * <p>
       * Returns the Lanczos approximation used to compute the gamma function.
       * The Lanczos approximation is related to the Gamma function by the
       * following equation
       * <center>
       * {@code gamma(x) = sqrt(2 * pi) / x * (x + g + 0.5) ^ (x + 0.5)
       * * exp(-x - g - 0.5) * lanczos(x)},
       * </center>
       * where {@code g} is the Lanczos constant.
       * </p>
       *
       * @param x Argument.
       * @return The Lanczos approximation.
       * @see <a href="http://mathworld.wolfram.com/LanczosApproximation.html">Lanczos Approximation</a>
       * equations (1) through (5), and Paul Godfrey's
       * <a href="http://my.fit.edu/~gabdo/gamma.txt">Note on the computation
       * of the convergent Lanczos complex Gamma approximation</a>
       * @since 3.1
       */
      public static double lanczos(final double x) {
          double sum = 0.0;
          for (int i = LANCZOS.length - 1; i > 0; --i) {
              sum += LANCZOS[i] / (x + i);
          }
          return sum + LANCZOS[0];
      }
  
      /**
       * Returns the value of 1 / &Gamma;(1 + x) - 1 for -0&#46;5 &le; x &le;
       * 1&#46;5. This implementation is based on the double precision
       * implementation in the <em>NSWC Library of Mathematics Subroutines</em>,
       * {@code DGAM1}.
       *
       * @param x Argument.
       * @return The value of {@code 1.0 / Gamma(1.0 + x) - 1.0}.
       * @since 3.1
       */
      public static double invGamma1pm1(final double x) {
          assert x >= -0.5;
          assert x <= 1.5;
  
          final double ret;
          final double t = x <= 0.5 ? x : (x - 0.5) - 0.5;
          if (t < 0.0) {
              final double a = INV_GAMMA1P_M1_A0 + t * INV_GAMMA1P_M1_A1;
              double b = INV_GAMMA1P_M1_B8;
              b = INV_GAMMA1P_M1_B7 + t * b;
              b = INV_GAMMA1P_M1_B6 + t * b;
              b = INV_GAMMA1P_M1_B5 + t * b;
              b = INV_GAMMA1P_M1_B4 + t * b;
              b = INV_GAMMA1P_M1_B3 + t * b;
              b = INV_GAMMA1P_M1_B2 + t * b;
              b = INV_GAMMA1P_M1_B1 + t * b;
              b = 1.0 + t * b;
  
              double c = INV_GAMMA1P_M1_C13 + t * (a / b);
              c = INV_GAMMA1P_M1_C12 + t * c;
              c = INV_GAMMA1P_M1_C11 + t * c;
              c = INV_GAMMA1P_M1_C10 + t * c;
              c = INV_GAMMA1P_M1_C9 + t * c;
              c = INV_GAMMA1P_M1_C8 + t * c;
              c = INV_GAMMA1P_M1_C7 + t * c;
              c = INV_GAMMA1P_M1_C6 + t * c;
              c = INV_GAMMA1P_M1_C5 + t * c;
              c = INV_GAMMA1P_M1_C4 + t * c;
              c = INV_GAMMA1P_M1_C3 + t * c;
              c = INV_GAMMA1P_M1_C2 + t * c;
              c = INV_GAMMA1P_M1_C1 + t * c;
              c = INV_GAMMA1P_M1_C + t * c;
              if (x > 0.5) {
                  ret = t * c / x;
              } else {
                  ret = x * ((c + 0.5) + 0.5);
              }
          } else {
              double p = INV_GAMMA1P_M1_P6;
              p = INV_GAMMA1P_M1_P5 + t * p;
              p = INV_GAMMA1P_M1_P4 + t * p;
              p = INV_GAMMA1P_M1_P3 + t * p;
              p = INV_GAMMA1P_M1_P2 + t * p;
              p = INV_GAMMA1P_M1_P1 + t * p;
              p = INV_GAMMA1P_M1_P0 + t * p;
  
              double q = INV_GAMMA1P_M1_Q4;
              q = INV_GAMMA1P_M1_Q3 + t * q;
              q = INV_GAMMA1P_M1_Q2 + t * q;
              q = INV_GAMMA1P_M1_Q1 + t * q;
              q = 1.0 + t * q;
  
              double c = INV_GAMMA1P_M1_C13 + (p / q) * t;
              c = INV_GAMMA1P_M1_C12 + t * c;
              c = INV_GAMMA1P_M1_C11 + t * c;
              c = INV_GAMMA1P_M1_C10 + t * c;
              c = INV_GAMMA1P_M1_C9 + t * c;
              c = INV_GAMMA1P_M1_C8 + t * c;
              c = INV_GAMMA1P_M1_C7 + t * c;
              c = INV_GAMMA1P_M1_C6 + t * c;
              c = INV_GAMMA1P_M1_C5 + t * c;
              c = INV_GAMMA1P_M1_C4 + t * c;
              c = INV_GAMMA1P_M1_C3 + t * c;
              c = INV_GAMMA1P_M1_C2 + t * c;
              c = INV_GAMMA1P_M1_C1 + t * c;
              c = INV_GAMMA1P_M1_C0 + t * c;
  
              if (x > 0.5) {
                  ret = (t / x) * ((c - 0.5) - 0.5);
              } else {
                  ret = x * c;
              }
          }
  
          return ret;
      }
  
      /**
       * Returns the value of log &Gamma;(1 + x) for -0&#46;5 &le; x &le; 1&#46;5.
       * This implementation is based on the double precision implementation in
       * the <em>NSWC Library of Mathematics Subroutines</em>, {@code DGMLN1}.
       *
       * @param x Argument.
       * @return The value of {@code log(Gamma(1 + x))}.
       * @since 3.1
       */
      public static double logGamma1p(final double x) {
          assert x >= -0.5;
          assert x <= 1.5;
          return -Math.log1p(invGamma1pm1(x));
      }
  }
  
  