[
https://issues.apache.org/jira/browse/NUMBERS-214?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Herbert resolved NUMBERS-214.
----------------------------------
Fix Version/s: 1.4
Assignee: Alex Herbert
Resolution: Implemented
Lowered max iterations in commit:
f5d0de6892bc701bd75beff80e6d9c374190fc09
> 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
> Assignee: Alex Herbert
> Priority: Trivial
> Fix For: 1.4
>
>
> 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)
