Skip to content
@ac-kit

Continued fractions

@ac-kit/math-analysisPortable

import { continuedFractionEval, ContinuedFraction } from "@ac-kit/math-analysis";

Where you meet it. Mostly underneath other things. The incomplete gamma and beta functions in this package are computed with continued fractions, because their power series becomes unusably slow exactly where the fraction becomes fast. Outside numerics they are how “best rational approximation” problems are solved — the reason a year is 365 + 97/400 days in the Gregorian calendar.

Evaluating one

Section titled “Evaluating one”

continuedFractionEval() takes a ContinuedFraction: two functions giving the aⱼ and bⱼ coefficients for any depth. Supplying them as functions rather than arrays is what lets a genuinely unbounded fraction be described in a few lines.

The evaluation works forwards, from b₀ outward, so it never has to decide in advance how deep to go. Each step multiplies the running value by a factor that tends towards 1, and the iteration stops once that factor is within tolerance of 1 — in other words, once another term would no longer change the answer.

The alternative, working backwards from the deepest term, has to pick a depth first and start over when the pick turns out to have been too shallow.

How fast a continued fraction converges

Lentz's method works forwards from b₀, so it needs no guess at where to truncate: each step multiplies the running value by a factor tending to 1, and the iteration stops when that factor is within tolerance of 1. The backward evaluation it replaces has to pick a depth up front and re-run the whole fraction when the pick was too shallow. Compare the three fractions — the periodic ones converge geometrically, Brouncker's crawls.

math-analysis/continued-fraction-eval.example.ts
const { fraction: coefficients, exact } = FRACTIONS[fraction];


const budgets: number[] = [];
const errors: number[] = [];


for (let budget = 1; budget <= terms; budget++) {
  const result = continuedFractionEval(coefficients, {
    maxIterations: budget,
    tolerance: 0,
  });
  budgets.push(budget);
  errors.push(Math.max(Math.abs(result.value - exact), Number.MIN_VALUE));
}


const frame = curveFrame(
  budgets,
  [{ name: "absolute error", values: errors }],
  { x: "terms", y: "error", series: "quantity" },
);

Like every iterative routine here, it can run out of budget before it runs out of work. It reports that rather than throwing — see convergence and iteration limits.

Further reading