Alex Herbert created NUMBERS-214:
------------------------------------
Summary: GeneralizedContinuedFraction has default max iterations
at 2^31 resulting in excess runtime for non-converging fractions
Key: NUMBERS-214
URL: https://issues.apache.org/jira/browse/NUMBERS-214
Project: Commons Numbers
Issue Type: Improvement
Components: fraction
Affects Versions: 1.3
Reporter: Alex Herbert
The GeneralizedContinuedFraction has a default number of iterations as the
limit of an integer. This far exceeds the number of iterations required for
convergence to double-precision of typical fractions. This can result in excess
runtime for fractions that will not converge.
An improvement is to set the default number of iterations to a lower value,
e.g. 1,000,000. This will bound the work performed before the maximum
iterations exception is raised.
The following series generates a fraction that oscillates and never converges:
{noformat}
final int[] calls = {0};
final Supplier<Coefficient> gen = () -> {
calls[0]++;
// The first term provides b0 to seed the evaluation (a is discarded).
// All subsequent terms (a=1, b=0) create a non-converging oscillation.
return Coefficient.of(1, calls[0] == 1 ? 1 : 0);
};
// Updated defaults
long time = System.nanoTime();
Assertions.assertThrows(ArithmeticException.class,
() -> GeneralizedContinuedFraction.value(gen, 0x1.0p-53, 1_000_000));
System.out.println((System.nanoTime() - time) * 1e-9);
// Current defaults
time = System.nanoTime();
Assertions.assertThrows(ArithmeticException.class,
() -> GeneralizedContinuedFraction.value(gen));
System.out.println((System.nanoTime() - time) * 1e-9);{noformat}
The runtimes (Java 8; MacOS M2 Pro):
||Max Iterations||Time (s)||
|1,000,000|0.045242416|
|2^31|12.474051125|
Note that the current behaviour can still be obtained by using the overloaded
method which accepts a maxIterations argument. This will allow the default
level to be raised for slowly converging fractions.
Issue identified using a security scanner.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
