Some Thoughts

The following method based on Taylor series may be more effective for trigonometric functions, especially for small \(\theta\). For larger angles, I suspect the easiest route is to compute cosines of a small angle and evaluate a Chebyshev or spread polynomial, possibly coupled with angle addition formulas.

The initial terms of the continued fraction expansion of \(\sin 1\) are readily calculated from the Taylor series \(\sin 1 = 1 - \frac{1}{3!} + \frac{1}{5!} - ...\). Compute the rational \(r\) resulting from evaluating the first \(k\) terms of Taylor series for some \(k\). We know \(r\) is an upper or lower bound for \(\sin 1\) of distance less than \(1/(2k-1)!\). Compute the continued fraction expansion \([a_1;a_2, ...]\) of \(r\) along with their convergents \(p_i/q_i\), stopping at the last \(p_i/q_i\) greater than \(r\) with \(2 q_i^2 < (2k-1)!\). This guarantees that \(|\sin 1 - p_i/q_i| < 1/(2k-1)! < 1/(2 q_i^2)\). By the bounds we derived \(p_i/q_i\) is a convergent for \(\sin 1\).

We can arbitrarily extend our continued fraction expansion by considering more of the Taylor series. Suppose \(p_i/q_i > \sin 1\), for we may reverse the signs below to handle the other case. Choose a larger even \(k\) and update \(r\), which becomes a lower bound for \(\sin 1\). Find the largest integer \(x\) satisfying

Thus we have a convergent lower than a lower bound of \(\sin 1\) (it is either what we seek, or an intermediate convergent). Obtain an upper bound on \(\sin 1\) by updating \(r\) with the next term of the Taylor series. Replace \(x\) with \(x + 1\) and see if the resulting convergent is larger than this upper bound. If so, we have found \(a_{i+1} = x\). If not, then we do not have enough information to tell which answer is correct, so we try again with a larger \(k\).

Repeat this procedure to find more terms and convergents. Naturally, this method works for any sequence where we can iteratively establish better upper and lower bounds:

In my current implementation, I only allow continued fraction expansions with positive terms. Thus if two successive numerators have the same sign, then all future numerators have the same sign, and similarly for the denominators. Provided that a sequence is not converging to zero (a moot point considering we cannot handle any sequence that converges to an integer; see below), we can compute terms and convergents until the signs have stabilized before feeding output to other algorithms. To simplify, once the sign is determined all negative numbers can be made positive.

We can obtain continued fractions for expressions composed of:

There are probably reasonable ways to get at algebraic numbers, at least the ones of lower degree.

It seems little is known about what can and can’t be easily expressed with continued fractions. We’re lucky to have the few sequences discovered so far, but I wish it were known how to do just a shade more. In particular, for one application (computing Hilbert class polynomials), I would like to be able to express \(e^{i\pi m/n}\) and \(e^{\pi m/n}\) as a sum of real and imaginary continued fractions for integers \(m\) and \(n\). The former is algebraic so perhaps we already have the means. The latter looks unassailable.

Consder more general numerators and denominators in the convergents. For example, what happens when \(i\) or \(\sqrt{5}\) appears in the table used to compute convergents? A division and remainder method of sorts should still be available, and it might be feasible to squeeze out the integer parts by Newton’s method, to produce integer continued fraction terms. This trick probably generalizes, suggesting we may be able to derive a continued fraction for exponential, trigonometric or hyperbolic trigonometric functions applied on algebraic numbers.

The above formulas give us a series of rational functions \(p(x)/q(x)\) that are approximations of some function \(f(x)\). If \(x\) is a transcendental and we know some sequence that converges to \(x\), one natural tactic is to substitute closer and closer convergents of \(x\) into \(p(x)/q(x)\) to find its integer part and hence a continued fraction expansion for \(f(x)\). I’m guessing the costs outweight the benefits.

We have ignored a major problem with continued fractions. If we square \(\sqrt{2} = [1;2,...]\) using the quadratic algorithm, we will never be able to output the first digit, as two successive convergents always have differing integer parts.

I read some papers that address some of the above, and am too lazy to summarize them:

They can be found online via Google Scholar.

AJ van der Poorten, Continued fractions of formal power series: let \(F_0, F_1, ...\) be the Fibonacci sequence. Then the continued fraction expansion of \(\sum_{i\ge 0} 2^{-F_i}\) often has very large terms, each of which dwarfs the previous one. Perhaps it could be used as a benchmark for continued fraction software.