Some Thoughts

We’ve claimed trigonometric functions can be computed using continued fractions using \(\tan(\theta/2)\) identities and the nonregular continued fraction expansion for \(\tan z\).

Unfortunately, all numerators in this expansion save the first are negative, implying that convergents strictly increase after the first. Thus our method for converting it to a regular continued fraction may produce \(0\) terms. Similarly, attempting decimal conversion may result in “digits” greater than 9.

Perhaps there’s a well-behaved expansion for \(\sin\) I don’t know about, or there’s ways to prove the sequence behaves after a finite number of terms. Or perhaps Gosper tolerates the 0 term, meaning that once in a while you may have to update previous answers.

Taylor Series

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 \lt (2k-1)!\). This guarantees that \(|\sin 1 - p_i/q_i| \lt 1/(2k-1)! \lt 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 \gt \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

\[ \begin{aligned} \frac { p_i x + p_{i-1}}{ q_i x + q_{i-1}} & \le & r \end{aligned} \]

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:

  • Using a Ramanujan formula for pi to compute its continued fraction expansion is probably faster than using an inverse tan expansion.

  • Starting just above and just below a root, we can use Newton’s method to generate sequences of upper and lower bounds. With the comparison test we can avoid error analysis.

Sign Stability

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.

Extending Our Reach

We can obtain continued fractions for expressions composed of:

  • integers and rationals

  • \(e\) and \(\pi\)

  • exponential functions, trigonometric functions and hyperbolic trigonometric functions and their inverses on rationals and their square roots

  • the four basic operations on continued fractions

  • square roots, and roots of quadratic equations when the coefficients are continued fractions.

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.

Converging to Integers

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.

References

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

  • Lester, “Effective Continued Fractions”

  • Vuillemin, “Exact Real Computer Arithmetic with Continued Fractions”

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.


Ben Lynn blynn@cs.stanford.edu 💡