[
https://issues.apache.org/jira/browse/NUMBERS-175?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17442817#comment-17442817
]
Alex Herbert edited comment on NUMBERS-175 at 11/15/21, 5:39 PM:
-----------------------------------------------------------------
Some more thoughts on implementations.
When using static functions with generators passed as an argument there is the
need to create either a lambda expression or more likely an anonymous class
that holds the current values for a and b so the next can be computed.
If an anonymous class must be created then it could be formalised as the means
to evaluate the value:
{code:java}
public abstract class GeneralizedContinuedFraction {
/**
* Create an instance that will iterate until convergence.
*/
public GeneralizedContinuedFraction();
/**
* Create an instance that will iterate until convergence on the specified
error.
* @param epsilon Maximum relative error allowed.
*/
public GeneralizedContinuedFraction(double epsilon);
/**
* Create an instance that will iterate until convergence on the specified
error
* or the maximum iterations is exceeded.
* @param epsilon Maximum relative error allowed.
* @param maxIterations Maximum number of iterations.
*/
public GeneralizedContinuedFraction(double epsilon, int maxIterations);
/**
* Defines the next partial numerator {@code a} and partial
* denominator {@code b} of the
* <a href="https://mathworld.wolfram.com/ContinuedFraction.html";>.
*
* @return the pair of coefficients {@code [a, b]}
*/
protected abstract double[] next();
/**
* Evaluates the continued fraction.
* This method can only be invoked once per instance.
*
* @return the value of the continued fraction
*/
public double value();
}
{code}
This would be used as:
{code:java}
// Golden ratio
final double gr = new GeneralizedContinuedFraction(epsilon) {
double[] r = {1, 1};
@Override
protected double[] next() {
return
}
}.value();
// Base of the natural logarithm e:
//
https://en.wikipedia.org/wiki/Continued_fraction#Regular_patterns_in_continued_fractions
// e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ...]
final double e1 = new GeneralizedContinuedFraction() {
int n;
// leading term does not follow the pattern
double t = 2;
@Override
protected double[] next() {
double[] r = {1, t};
// Repeating series of 3:
// [1, t, 1] where t = 2 + 2 n/3
n++;
t = n % 3 == 2 ? 2 + 2 * (n / 3) : 1;
return r;
}
}.value();
final double e2 = new GeneralizedContinuedFraction() {
int n;
// leading term does not follow the pattern so is added afterwards
double t = 0;
@Override
protected double[] next() {
double[] r = {1, t};
// Repeating series of 3:
// [1, t, 1] where t = 2 + 2 n/3
n++;
t = n % 3 == 2 ? 2 + 2 * (n / 3) : 1;
return r;
}
}.value() + 2;
{code}
The second example to evaluate E is performed twice:
* e1 includes the leading term b0 as 2 in the evaluation
* e2 adds this term after the fraction is evaluated
On my test example (based on the modified Lentz algorithm in ContinuedFraction)
the second value e2 is an exact match to Math.E. The value e1 is out by 2 ULP.
I created a variation that uses both terms a0 and b0 and evaluated the fraction
without the leading 2. This also computes E exactly. This adds some support to
allow evaluation with and without the leading term b0.
h3. Possible Issues with class instances
Allowing creation of a class which can be used 1 time for the call to evaluate
the result is open to possible usage error. This could be guarded against by
caching the result and returning it on subsequent calls. Ideally would also
raise the same exceptions on subsequent invocations when the evaluation fails.
Caching the result would have a minor performance impact.
h3. Static method with a generator
If implemented with a static method passed a generator then the methods can be
added to the current ContinuedFraction class. That class then allows usage
through the current API to support multiple use evaluation for different
argument x with an instance, or single use evaluation with a generator of the
coefficients and a static method call.
There would be no need for GeneralizedContinuedFraction and
SimpleContinuedFraction classes as the static method signature would be
different. The implementation to compute the value is the same; the method only
requires a generator for a and b, or just b with a=1.
h3. Pairs of coefficients
Should coefficient pairs be returned as a double[] or formalised as a class:
{code:java}
final class Coefficient {
static Coefficient of(double a, double b);
double getA();
double getB();
}{code}
was (Author: alexherbert):
Some more thoughts on implementations.
When using static functions with generators passed as an argument there is the
need to create either a lambda expression or more likely an anonymous class
that holds the current values for a and b so the next can be computed.
If an anonymous class must be created then it could be formalised as the means
to evaluate the value:
{code:java}
public abstract class GeneralizedContinuedFraction {
/**
* Create an instance that will iterate until convergence.
*/
public GeneralizedContinuedFraction();
/**
* Create an instance that will iterate until convergence on the specified
error.
* @param epsilon Maximum relative error allowed.
*/
public GeneralizedContinuedFraction(double epsilon);
/**
* Create an instance that will iterate until convergence on the specified
error
* or the maximum iterations is exceeded.
* @param epsilon Maximum relative error allowed.
* @param maxIterations Maximum number of iterations.
*/
public GeneralizedContinuedFraction(double epsilon, int maxIterations);
/**
* Defines the next partial numerator {@code a} and partial
* denominator {@code b} of the
* <a href="https://mathworld.wolfram.com/ContinuedFraction.html";>.
*
* @return the pair of coefficients {@code [a, b]}
*/
protected abstract double[] next();
/**
* Evaluates the continued fraction.
* This method can only be invoked once per instance.
*
* @return the value of the continued fraction
*/
public double value();
}
{code}
This would be used as:
{code:java}
// Golden ratio
final double gr = new GeneralizedContinuedFraction(epsilon) {
double[] r = {1, 1};
@Override
protected double[] next() {
return
{code}
{color:#910091}r{color}
{code:java}
;
}
}.value();
// Base of the natural logarithm e:
//
https://en.wikipedia.org/wiki/Continued_fraction#Regular_patterns_in_continued_fractions
// e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ...]
final double e1 = new GeneralizedContinuedFraction() {
int n;
// leading term does not follow the pattern
double t = 2;
@Override
protected double[] next() {
double[] r = {1, t};
// Repeating series of 3:
// [1, t, 1] where t = 2 + 2 n/3
n++;
t = n % 3 == 2 ? 2 + 2 * (n / 3) : 1;
return r;
}
}.value();
final double e2 = new GeneralizedContinuedFraction() {
int n;
// leading term does not follow the pattern so is added afterwards
double t = 0;
@Override
protected double[] next() {
double[] r = {1, t};
// Repeating series of 3:
// [1, t, 1] where t = 2 + 2 n/3
n++;
t = n % 3 == 2 ? 2 + 2 * (n / 3) : 1;
return r;
}
}.value() + 2;
{code}
The second example to evaluate E is performed twice:
* e1 includes the leading term b0 as 2 in the evaluation
* e2 adds this term after the fraction is evaluated
On my test example (based on the modified Lentz algorithm in ContinuedFraction)
the second value e2 is an exact match to Math.E. The value e1 is out by 2 ULP.
I created a variation that uses both terms a0 and b0 and evaluated the fraction
without the leading 2. This also computes E exactly. This adds some support to
allow evaluation with and without the leading term b0.
h3. Possible Issues with class instances
Allowing creation of a class which can be used 1 time for the call to evaluate
the result is open to possible usage error. This could be guarded against by
caching the result and returning it on subsequent calls. Ideally would also
raise the same exceptions on subsequent invocations when the evaluation fails.
Caching the result would have a minor performance impact.
h3. Static method with a generator
If implemented with a static method passed a generator then the methods can be
added to the current ContinuedFraction class. That class then allows usage
through the current API to support multiple use evaluation for different
argument x with an instance, or single use evaluation with a generator of the
coefficients and a static method call.
There would be no need for GeneralizedContinuedFraction and
SimpleContinuedFraction classes as the static method signature would be
different. The implementation to compute the value is the same; the method only
requires a generator for a and b, or just b with a=1.
h3. Pairs of coefficients
Should coefficient pairs be returned as a double[] or formalised as a class:
{code:java}
final class Coefficient {
static Coefficient of(double a, double b);
double getA();
double getB();
}{code}
> 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)
