Class GeneralizedContinuedFraction

java.lang.Object
org.apache.commons.numbers.fraction.GeneralizedContinuedFraction

public final class GeneralizedContinuedFraction extends Object
Provides a means to evaluate generalized continued fractions.

The continued fraction uses the following form for the numerator (a) and denominator (b) coefficients:

              a1
 b0 + ------------------
      b1 +      a2
           -------------
           b2 +    a3
                --------
                b3 + ...
 

A generator of the coefficients must be provided to evaluate the continued fraction.

The implementation of the fraction evaluation is based on the modified Lentz algorithm as described on page 508 in:

Since:
1.1
See Also:
  • Field Details

    • SMALL

      static final double SMALL
      The value for any number close to zero.

      "The parameter small should be some non-zero number less than typical values of eps * |b_n|, e.g., 1e-50".

      See Also:
    • DEFAULT_ITERATIONS

      static final int DEFAULT_ITERATIONS
      Default maximum number of iterations.
      See Also:
    • MIN_EPSILON

      private static final double MIN_EPSILON
      Minimum relative error epsilon. Equal to 1 - Math.nextDown(1.0), or 2^-53.

      The epsilon is used to compare the change in the magnitude of the fraction convergent to 1.0. In theory eps can be 2^-53 reflecting the smallest reduction in magnitude possible i.e. next = previous * Math.nextDown(1.0), or zero reflecting exact convergence.

      If set to zero then the algorithm requires exact convergence which may not be possible due to floating point error in the algorithm. For example the golden ratio will not converge.

      The minimum value will stop the recursive evaluation at the smallest possible increase or decrease in the convergent.

      See Also:
    • MAX_EPSILON

      private static final double MAX_EPSILON
      Maximum relative error epsilon. This is configured to prevent incorrect usage. Values higher than 1.0 invalidate the relative error lower bound of (1 - eps) / 1. Set to 0.5 which is a very weak relative error tolerance.
      See Also:
    • DEFAULT_LOW

      private static final double DEFAULT_LOW
      Default low threshold for change in magnitude. Precomputed using MIN_EPSILON. Equal to 1 - 2^-53.
      See Also:
    • DEFAULT_EPS

      private static final double DEFAULT_EPS
      Default absolute difference threshold for change in magnitude. Precomputed using MIN_EPSILON. Equal to 1 / (1 - 2^-53) = 2^-52.
      See Also:
  • Constructor Details

    • GeneralizedContinuedFraction

      private GeneralizedContinuedFraction()
      No instances.
  • Method Details

    • value

      public static double value(Supplier<GeneralizedContinuedFraction.Coefficient> gen)
      Evaluates the continued fraction.

      Note: The first generated partial numerator a0 is discarded.

      Parameters:
      gen - Generator of coefficients.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • value

      public static double value(Supplier<GeneralizedContinuedFraction.Coefficient> gen, double epsilon)
      Evaluates the continued fraction.

      Note: The first generated partial numerator a0 is discarded.

      Parameters:
      gen - Generator of coefficients.
      epsilon - Maximum relative error allowed.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • value

      public static double value(Supplier<GeneralizedContinuedFraction.Coefficient> gen, double epsilon, int maxIterations)
      Evaluates the continued fraction.
                    a1
       b0 + ------------------
            b1 +      a2
                 -------------
                 b2 +    a3
                      --------
                      b3 + ...
       

      Setting coefficient an to zero will signal the end of the recursive evaluation.

      Note: The first generated partial numerator a0 is discarded.

      Usage Note

      This method is not functionally identical to calling value(double, Supplier, double, int) with the generator configured to provide coefficients from n=1 and supplying b0 separately. In some cases the computed result from the two variations may be different by more than the provided epsilon. The other method should be used if b0 is zero or very small. See the corresponding javadoc for details.

      Parameters:
      gen - Generator of coefficients.
      epsilon - Maximum relative error allowed.
      maxIterations - Maximum number of iterations.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • value

      public static double value(double b0, Supplier<GeneralizedContinuedFraction.Coefficient> gen)
      Evaluates the continued fraction.

      Note: The initial term b0 is supplied as an argument. Both of the first generated terms a and b are used. This fraction evaluation can be used when:

      • b0 is not part of a regular series
      • b0 is zero and the result will evaluate only the continued fraction component
      • b0 is very small and the result is expected to approach zero
      Parameters:
      b0 - Coefficient b0.
      gen - Generator of coefficients.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • value

      public static double value(double b0, Supplier<GeneralizedContinuedFraction.Coefficient> gen, double epsilon)
      Evaluates the continued fraction.

      Note: The initial term b0 is supplied as an argument. Both of the first generated terms a and b are used. This fraction evaluation can be used when:

      • b0 is not part of a regular series
      • b0 is zero and the result will evaluate only the continued fraction component
      • b0 is very small and the result is expected to approach zero
      Parameters:
      b0 - Coefficient b0.
      gen - Generator of coefficients.
      epsilon - Maximum relative error allowed.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • value

      public static double value(double b0, Supplier<GeneralizedContinuedFraction.Coefficient> gen, double epsilon, int maxIterations)
      Evaluates the continued fraction.
                    a1
       b0 + ------------------
            b1 +      a2
                 -------------
                 b2 +    a3
                      --------
                      b3 + ...
       

      Setting coefficient an to zero will signal the end of the recursive evaluation.

      Note: The initial term b0 is supplied as an argument. Both of the first generated terms a and b are used. This fraction evaluation can be used when:

      • b0 is not part of a regular series
      • b0 is zero and the result will evaluate only the continued fraction component
      • b0 is very small and the result is expected to approach zero

      Usage Note

      This method is not functionally identical to calling value(Supplier, double, int) with the generator configured to provide term "b0" in the first coefficient. In some cases the computed result from the two variations may be different by more than the provided epsilon. The convergence of the continued fraction algorithm relies on computing an update multiplier applied to the current value. Convergence is faster if the initial value is close to the final value. The value(Supplier, double, int) method will initialise the current value using b0 and evaluate the continued fraction using updates computed from the generated coefficients. This method initialises the algorithm using b1 to evaluate part of the continued fraction and computes the result as:

              a1
       b0 + ------
             part
       

      This is preferred if b0 is smaller in magnitude than the continued fraction component. In particular the evaluation algorithm sets a bound on the minimum initial value as 1e-50. If b0 is smaller than this value then using this method is the preferred evaluation.

      Parameters:
      b0 - Coefficient b0.
      gen - Generator of coefficients.
      epsilon - Maximum relative error allowed.
      maxIterations - Maximum number of iterations.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
      See Also:
    • evaluate

      static double evaluate(double b0, Supplier<GeneralizedContinuedFraction.Coefficient> gen, double epsilon, int maxIterations)
      Evaluates the continued fraction using the modified Lentz algorithm described in Thompson and Barnett (1986) Journal of Computational Physics 64, 490-509.
                    a1
       b0 + ------------------
            b1 +      a2
                 -------------
                 b2 +    a3
                      --------
                      b3 + ...
       

      Note: The initial term b0 is supplied as an argument. Both of the first generated terms a and b are used.

      Implementation Note

      This method is private and functionally different from value(double, Supplier, double, int). The convergence of the algorithm relies on computing an update multiplier applied to the current value, initialised as b0. Accuracy of the evaluation can be effected if the magnitude of b0 is very different from later terms. In particular if initialised as 0 the algorithm will not function and so must set b0 to a small non-zero number. The public methods with the leading b0 term provide evaluation of the fraction if the term b0 is zero.

      Parameters:
      b0 - Coefficient b0.
      gen - Generator of coefficients.
      epsilon - Maximum relative error allowed.
      maxIterations - Maximum number of iterations.
      Returns:
      the value of the continued fraction.
      Throws:
      ArithmeticException - if the algorithm fails to converge or if the maximal number of iterations is reached before the expected convergence is achieved.
    • updateIfCloseToZero

      private static double updateIfCloseToZero(double value)
      Returns the value, or if close to zero returns a small epsilon of the same sign.

      This method is used in Thompson & Barnett to monitor both the numerator and denominator ratios for approaches to zero.

      Parameters:
      value - the value
      Returns:
      the value (or small epsilon)