FOUNDATION SERVICES - Continued fractions with infinities

Continued fractions with infinities

Continued fraction approximations, while not widely used on pre-IEEE platforms, are powerful tools. Here is a function f that takes the values 1, 1, 3/5, 2/5, and 5/17 at the values x = 0, 1, 2, 3, and 4, respectively.

The function f is well behaved, as the graph in the margin shows. Until recently continued fraction formulations had been avoided as too slow; division was slow in hardware, relegated to software, or just too troublesome because of the possibility of division by zero. Instead, most texts suggested the mathematically equivalent rational function approximation. Unfortunately, the rational function may overflow or underflow if the argument is at the extremes of the exponent range and no accumulator with wider exponent range is available. It tends to suffer more rounding error, too. The problem is worse for higher-order formulations.

Evaluating a continued fraction is similar to Horner's recurrence for polynomials. In this instance, the coefficients are passed in arrays.

  float Interpolator(float x, int n, float *p, float *q) {
      float_t sum = p[n];     // bottommost coefficient
      for (int i = n - 1; i >= 0; i--)
          sum = p[i] + ((float_t) x + q[i]) / sum;
      return sum;
  }

When x is 0.5, the expression (17.5 + (x-4)/0.2) is zero (even though

must be rounded), so divide-by-zero occurs; but the resulting

passes through the rest of the expression without incident, and the correct result 1.2 is obtained.

This particular program is not defined for an infinite argument, because the expression results in a NaN. (No numerical value for yields a satisfactory result from both the continued function and its mathematically equivalent rational function at and .) A robust version of Interpolator filters infinite arguments with code such as:

  if (IsInfinite(x))
      return 1.0 / x;

Interpolator(kInfinity) is

, indicating that the function approaches zero from above for large arguments. Similarly, Interpolator(-kInfinity) is

, indicating that the function approaches zero from below for large negative arguments. The next section discusses the sign of zero further.

[Contents] [Previous] [Next]

Click the icon to mail questions or corrections about this material to Taligent personnel.

Generated with WebMaker