[
https://issues.apache.org/jira/browse/NUMBERS-175?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17444541#comment-17444541
]
Alex Herbert commented on NUMBERS-175:
--------------------------------------
{quote}Did you intend to provide...
{quote}
I did think of:
{code:java}
public final class SimpleContinuedFraction {
public static double value(double b0, double... b);
public static double value(double... b);
}
{code}
When the list of partial denominator coefficients is finite then the fraction
can be evaluated using the coefficients in reverse without any iteration
tolerance checks:
{code:java}
static double simpleContinuedFraction(double b0, double... b) {
int length = b.length;
if (length == 0) {
return b0;
}
double term = 1 / b[length - 1];
for (int i = length - 2; i >= 0; i--) {
term = 1 / (b[i] + term);
}
return b0 + term;
}
@Test
void test() {
// 415 / 93 == [4; 2, 6, 7]
double expected = 415.0 / 93;
Assertions.assertEquals(expected, simpleContinuedFraction(4, 2, 6, 7),
Math.ulp(expected));
}{code}
I am not sure if this is a stable algorithm compared to the modified Lentz
algorithm that starts with the first term. It requires that each coefficient is
non-zero so some checks would be required. Any errors in the initial terms may
propagate to larger errors due to the recursive use of the reciprocal.
For a simple regular continued fraction the coefficients would be non-zero
integers but that use case would be covered by using double arguments anyway.
h3. Note
Separation of the initial term b0 as an argument allows support for evaluating
with and without the initial term. Using the original static method call API:
{code:java}
public static final class GeneralizedContinuedFraction {
/**
* Evaluate the continued fraction from the generator for partial numerator
* a and partial denominator b.
* <pre>
* b0 + a1
* ------------------
* b1 + a2
* -------------
* b2 + a3
* --------
* b3 + ...
* </pre>
*
* <p>Note: The first generated partial numerator a0 is discarded.
*
* @param gen Generator
* @return the continued fraction value
*/
public static double value(Supplier<double[]> gen);
/**
* Evaluate the continued fraction from the generator for partial numerator
* a and partial denominator b.
* <pre>
* b0 + a1
* ------------------
* b1 + a2
* -------------
* b2 + a3
* --------
* b3 + ...
* </pre>
*
* <p>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 term b0 is not part of a regular series. Set it
* to zero to evaluate only the continued fraction component.
*
* @param gen Generator
* @return the continued fraction value
*/
public static double value(double b0, Supplier<double[]> gen);
}
{code}
I prefer the static method call API as it emphasises the supplied generator
argument is for one time usage.
I have benchmarked use of Supplier<double[]> against Supplier<Coefficient> and
there is no difference. The use of a Coefficient class to encapsulate a and b
does avoid incorrect usage.
To support an array of partial denominators does not require a max iterations
argument as the maximum is limited by the number of denominators. An epsilon
could be supplied but this can be confused with the varargs term. In this case
I would suggest not having an epsilon and using the machine epsilon. This then
has the following API:
{code:java}
public static final class GeneralizedContinuedFraction {
public static final class Coefficient {
public double getA();
public double getB();
public static Coefficient of(double a, double b);
}
public static double value(Supplier<Coefficient> gen);
public static double value(Supplier<Coefficient> gen, double epsilon);
public static double value(Supplier<Coefficient> gen, double epsilon, int
maxIterations);
public static double value(double b0, Supplier<Coefficient> gen);
public static double value(double b0, Supplier<Coefficient> gen, double
epsilon);
public static double value(double b0, Supplier<Coefficient> gen, double
epsilon, int maxIterations);
}
public static final class SimpleContinuedFraction {
public static double value(DoubleSupplier gen);
public static double value(DoubleSupplier gen, double epsilon);
public static double value(DoubleSupplier gen, double epsilon, int
maxIterations);
public static double value(double b0, DoubleSupplier gen);
public static double value(double b0, DoubleSupplier gen, double epsilon);
public static double value(double b0, DoubleSupplier gen, double epsilon,
int maxIterations);
// No convergence epsilon
public static double valueA(double... b);
public static double valueB(double b0, double... b);
}
{code}
The simple continued fraction can be evaluated using the generalized continued
fraction and setting all numerators a to 1. So it is a convenience rather than
a necessary. It does provided a place to put the helper function with the var
args signature as this only applies to simple continued fractions. Due to the
use of varargs the methods must be distinguished by name so the compiler knows
which to call. To simplify the initial API these can be dropped, or replaced
with a helper function to convert a varargs array into a DoubleSupplier to be
passed to an evaluation method.
I do not desire to support a Stream as an input argument and would stick to the
supplier pattern. The overhead of creating objects to start the stream is
higher and the implementation must act as a terminating operation for the
stream which requires a lot more complexity.
> Add continued fraction implementations using a generator of terms
> -----------------------------------------------------------------
>
> Key: NUMBERS-175
> URL: https://issues.apache.org/jira/browse/NUMBERS-175
> Project: Commons Numbers
> Issue Type: Improvement
> Components: fraction
> Affects Versions: 1.0
> Reporter: Alex Herbert
> Priority: Minor
>
> The ContinuedFraction class allows computation of:
> {noformat}
> b0 + a1
> ------------------
> b1 + a2
> -------------
> b2 + a3
> --------
> b3 + ...{noformat}
> This is done using an abstract class that is extended to implement the
> methods to get the terms:
> {code:java}
> double getA(int n, double x);
> double getB(int n, double x);{code}
> This allows the fraction to be reused to generate results for different
> points to evaluate. However:
> * It does not lend itself to fractions where the terms can be computed using
> recursion:
> {noformat}
> b(n+1) = f( b(n) ) {noformat}
> * It requires two method calls to generate terms a_n and b_n for each
> iteration thus preventing optimisation of the computation using the input n
> for values shared between computation of a and b.
> An alternative method is to support a generator of the paired terms a_n and
> b_n:
> {code:java}
> static double continuedFraction(Supplier<double[]> gen);{code}
> To be used in a single evaluation as:
> {code:java}
> Supplier<double[]> goldenRatio = () -> return new double[] {1, 1};
> double gr = continuedFraction(goldenRatio);
> // gr = 1.61803398874...{code}
> An additional feature is to support a simple continued fraction where all
> partial numerators are 1:
> {noformat}
> b0 + 1
> ------------------
> b1 + 1
> -------------
> b2 + 1
> --------
> b3 + ...
> {noformat}
> E.g. using:
> {code:java}
> static double simpleContinuedFraction(DoubleSupplier gen); {code}
> h3. Addition
> In some situations it is an advantage to not evaluate the leading term b0.
> The term may not be part of a regular series, or may be zero:
> {noformat}
> a1
> ------------------
> b1 + a2
> -------------
> b2 + a3
> --------
> b3 + ...
> {noformat}
> h3. API
> Using the nomeclature from Wikipedia and Wolfram suggests the following:
> {code:java}
> public static final class GeneralizedContinuedFraction {
> /**
> * Evaluate the continued fraction from the generator for partial
> numerator
> * a and partial denominator b.
> * <pre>
> * b0 + a1
> * ------------------
> * b1 + a2
> * -------------
> * b2 + a3
> * --------
> * b3 + ...
> * </pre>
> *
> * <p>Note: The first generated partial numerator a0 is discarded.
> *
> * @param gen Generator
> * @return the continued fraction value
> */
> public static double value(Supplier<double[]> gen);
> /**
> * Evaluate the continued fraction from the generator for partial
> numerator
> * a and partial denominator b.
> * <pre>
> * a1
> * ------------------
> * b1 + a2
> * -------------
> * b2 + a3
> * --------
> * b3 + ...
> * </pre>
> *
> * <p>Note: Both of the first terms a and b are used.
> *
> * @param gen Generator
> * @return the continued fraction value
> */
> public static double valueA(Supplier<double[]> gen);
> }
> public static final class SimpleContinuedFraction {
> public static double value(DoubleSupplier gen);
> public static double valueA(DoubleSupplier gen);
> }
> {code}
> The API should support the optional parameters to control the convergence
> tolerance and the maximum number of iterations.
> The variant to evaluate without the leading b0 term is not essential. It can
> be evaluated by starting the generator at the next iteration using:
> {code:java}
> Supplier<double[]> gen = ...; // Start at terms (a1,b1)
> // Evaluation will discard a1;
> // this value (separately computed) is then used to compute the result
> double value = a1 / GeneralizedContinuedFraction.value(gen);{code}
> This variant is present in the Boost c++ library and used to evaluate terms
> for the gamma function.
> See:
> [https://en.wikipedia.org/wiki/Continued_fraction]
> [https://mathworld.wolfram.com/SimpleContinuedFraction.html]
> [https://mathworld.wolfram.com/GeneralizedContinuedFraction.html]
> [Boost Continued Fraction (v
> 1_77_0)|https://www.boost.org/doc/libs/1_77_0/libs/math/doc/html/math_toolkit/internals/cf.html]
>
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
