[NUMBERS-173] ContinuedFraction will infinite loop with zero epsilon

• Type: Bug
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 1.0
• Fix Version/s: 1.1
• Component/s: fraction
• Assignee: Unassigned
• Reporter: Alex Herbert
• Created: 01/Nov/21 18:27
• Updated: 01/Nov/22 11:00
• Resolved: 02/Nov/21 10:56

Description

The ContinuedFraction uses the following termination conditions for the loop:

while (n <= maxIterations) {

    // deltaN = relative factor applied to the current sum (hN)

    if (Math.abs(deltaN - 1) < epsilon) {
        return hN;
    }

    ++n;
}

If maxIterations is Integer.MAX_VALUE (the default) then n can never exceed this value as the integer will overflow to negative and the loop continues. Termination will only occur if the relative change is less than epsilon. For termination to occur:

• maxIterations must be less than Integer.MAX_VALUE; or
• epsilon must be set to the epsilon for a double (2^-52)

The following will infinite loop:

@Test
void testEpsilonZero() {
    ContinuedFraction cf = new ContinuedFraction() {
        @Override
        public double getA(int n, double x) {
            return 1;
        }

        @Override
        public double getB(int n, double x) {
            return 1;
        }
    };

    final double eps = 0.0;

    // Infinite loop when iterations has no limit
    Assertions.assertTimeoutPreemptively(Duration.of(500, ChronoUnit.MILLIS),
        () -> cf.evaluate(0, eps), "Continued fraction failed to converge");
}

Note that for the computation of the Golden ratio above, if the max iterations is set to a value smaller than Integer.MAX_VALUE then the deltaN term converges to 1 - Math.ulp(1.0), i.e. 0.999999999...

The fraction thus continues to get smaller and walks away from the ideal result. I modified the code to not throw an exception and return the current value when maxIterations is exceeded. The optimum should stop at 38 iterations.

for (int i = 35; i < 45; i++) {
    System.out.printf("%9d  %s%n", i, cf.evaluate(0, eps, i));
}
for (int i = 100; i < 1000000000; i*=10) {
    System.out.printf("%9d  %s%n", i, cf.evaluate(0, eps, i));
}

Outputs:

Expected:
           1.618033988749894848204586834365638117720309

       35  1.6180339887498971
       36  1.618033988749894
       37  1.6180339887498951
       38  1.618033988749895    *** Optimum ***
       39  1.6180339887498947
       40  1.6180339887498945
       41  1.6180339887498942
       42  1.618033988749894
       43  1.6180339887498938
       44  1.6180339887498936
      100  1.6180339887498811
     1000  1.6180339887496813
    10000  1.618033988747683
   100000  1.6180339887276989
  1000000  1.6180339885278587
 10000000  1.6180339865294573
100000000  1.6180339665454428

This can be fixed by validating the input epsilon using:

final double eps = epsilon > 0x1.0p-52 ? epsilon : 0x1.0p-52;

This will be robust to a NaN epsilon.