Continued Fractions

1 Background

For years, you’ve used \(22/7\) as an approximation for \(\pi\). But where does this number come from?

It’s from the continued fraction for \(\pi\). It’s called a convergent, and there are elegant results connecting convergents to the best rational approximations of numbers.

Continued fractions provide an alternate representation of numbers. Indeed, by unrolling more and more terms of the continued fraction, we can obtain better and better approximations of the number. Note that if the number we’re representing is irrational (meaning it does not have an exact rational representation), then its continued fraction must necessarily be infinite. By using a suitable data structure (think stream!), we get to represent this irrational number and obtain better and better rational approximations for it.

2 Example

Consider trying to approximate the square root of 2. First, note that we can rewrite the square root of two in terms of itself:Thanks to this equation.

\[\sqrt 2 = 1 + \frac{1}{1+\sqrt{2}}\]

We can then substitute the entire equation back into itself:

\[\sqrt 2 = 1 + \frac{1}{1+1 + \frac{1}{1+\sqrt{2}}} = \sqrt 2 = 1 + \frac{1}{2 + \frac{1}{1+\sqrt{2}}}\]

We can repeat this an infinite number of times:

\[\sqrt 2 = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2+\frac{1}{1 + ...}}}}\]

This endless tower is the continued fraction. We can truncate it at any point to arrive at the \(n\)th approximation: 1, 1.5, 1.4, etc.

3 Definition

In general, a simple continued fraction has the form

\[a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3+\frac{1}{a_4 + ...}}}}\]

where the \(a_i\) are called the coefficients of the continued fraction. (It’s simple because all the numerators are 1.)

We get the \(n\)th approximation by truncating the continued fraction at \(a_n\). For example, the third approximation is:

\[a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3}}}\]

We define a continued fraction stream as a stream of approximations of the represented number. As we take more and more entries from our continued fraction stream, the values get closer and closer to the true value of the irrational number.

4 Assignment: Part 1: Infinite Sequences

Some continued fractions have coefficients with repeating patterns. Write a function that, given a list, produces a stream that repeats the list over and over. Assume the given list is non-empty.

repeating-stream :: List<Number> -> Stream<Number>

5 Assignment: Part 2: Possibly Finite Sequences

Sometimes, a continued fraction is finite. This naturally happens when the number being represented is itself rational. That is, a finite continued fraction with \(n\) coefficients has the same form as the \(n\)th approximation of an infinite continued fraction.

However, there is another way we can “run out of coefficients”. It can also happen for irrational numbers when the coefficients have no known pattern—so we cannot write a program that generates the coefficients—and at some point we no longer know what coefficient comes next. (Maybe nobody knows, or maybe it’s just us; either way, our program needs to be able to handle this situation.)

In these cases, the coefficients actually form a list. However, it is inconvenient to have some continued fractions represented as lists and others as streams; it’s simpler to use one uniform representation for all of them. Therefore, we need some way of indicating, in the stream, “beyond this we do not know any more coefficients”. We will do this using the option type: all known values are represented as some, while a none represents the end of the known values (with the invariant that all subsequent values in the stream will also be none). Thus, a non-terminating stream of coefficients (and hence of approximations) now becomes of type Stream<Option<Number>>.

6 Analysis

Please analyze the big-O complexity of each of the operations above. What are the meaningful parameter(s) for your analysis?

7 Template Files

Implementation

Final Tests

8 Handing In

Implementation and Analysis