[jira] [Comment Edited] (NUMBERS-175) Add continued fraction implementations using a generator of terms
[
https://issues.apache.org/jira/browse/NUMBERS-175?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17445445#comment-17445445
]
Alex Herbert edited comment on NUMBERS-175 at 11/22/21, 2:36 PM:
-
I have started on an implementation using the generator approach.
Work in progress here [PR
109|https://github.com/apache/commons-numbers/pull/109].
I found some issues with the current implementation.
h3. It cannot compute values approaching zero with a small first term
Consider the evaluation of tan(z):
{noformat}
z
tan(z) = ---
1 - z^2
---
3 - z^2
---
5 - ...
{noformat}
Here the leading term is zero. The current implementation must set this to a
non-zero small number as an estimate of the first convergent h0. The remaining
convergents h1, h2, h3, etc are computed using an update to the first.
If the expected value is far from the initial non-zero number then this works.
Otherwise the result is incorrect:
{code:java}
@Test
void test() {
// Evaluate tan(x)
ContinuedFraction cf = new ContinuedFraction() {
@Override
protected double getA(int n, double x) {
return n == 1 ? x : -x * x;
}
@Override
protected double getB(int n, double x) {
return n == 0 ? 0 : 2 * n - 1;
}
};
for (double x : new double[] {0.1, 1e-2, 1e-4, 1e-6, 1e-50, 1e-100,
1e-200}) {
try {
System.out.printf("%25s %25s%n", Math.tan(x), cf.evaluate(x,
1e-10));
} catch (ArithmeticException ex) {
// failed
}
}
}
{code}
Outputs:
{noformat}
0.100334672085450550.10033467208545055
0.0146667207 0.0146667207
1.3334E-4 1.3334E-4
1.E-6 1.E-6
1.0E-502.0E-50
1.0E-1001.0E-50
1.0E-2001.0E-50
{noformat}
This is not a major issue as you can evaluate the fraction advanced by 1
iteration and then divide the original first numerator coefficient a1 by the
evaluated fraction:
{code:java}
@Test
void test() {
// Evaluate tan(x)
ContinuedFraction cf = new ContinuedFraction() {
@Override
protected double getA(int n, double x) {
return -x * x;
}
@Override
protected double getB(int n, double x) {
return 2 * n + 1;
}
};
for (double x : new double[] {0.1, 1e-2, 1e-4, 1e-6, 1e-50, 1e-100,
1e-200}) {
try {
System.out.printf("%25s %25s%n", Math.tan(x), x / cf.evaluate(x,
1e-10));
} catch (ArithmeticException ex) {
// failed
}
}
}
{code}
This is correct:
{noformat}
0.100334672085450550.10033467208545054
0.0146667207 0.0146667205
1.3334E-4 1.3334E-4
1.E-6 1.E-6
1.0E-501.0E-50
1.0E-100 1.0E-100
1.0E-200 1.0E-200
{noformat}
h3. It does not detect an update multiplier that is zero
Consider this very bad fraction using max value for the numerator after a few
terms:
{noformat}
1
0.5 + -
0.5 + max
---
0.5 +max
-
0.5 + ...
{noformat}
This will infinite loop:
{code:java}
@Test
void test() {
// This will create an update deltaN of zero.
// The algorithm gets stuck in a continuous loop.
ContinuedFraction cf = new ContinuedFraction() {
@Override
protected double getA(int n, double x) {
return n < 2 ? 1 : Double.MAX_VALUE;
}
@Override
protected double getB(int n, double x) {
return 0.5;
}
};
final double x = 1; // Ignored
Assertions.assertTimeoutPreemptively(Duration.ofSeconds(5),
() -> cf.evaluate(x, 1e-10));
}
{code}
The infinite loop is not detected due to the use of:
{code:java}
while (n <= maxIterations) {
{code}
With maxIterations set to Integer.MAX_VALUE this will loop forever. This
condition is mentioned in NUMBERS-46 but it was not fixed so that the algorithm
can enter at least 1 iteration.
This is a bug. I've fixed it in the PR above for the new generalized continued
fraction. An appropriate fix should be implemented in the ContinuedFraction
class.
was (Author: alexherbert):
I have started on an implementation using the generator approach.
Work in progress here [PR
109|https
[jira] [Comment Edited] (NUMBERS-175) Add continued fraction implementations using a generator of terms
[
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
* 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 impl
