Continued Fractions

1Background

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.

2Theme Song

Unwritten by Natasha Bedingfield

3Example

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.

4Definition

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 (counting from the 0th) 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. How can we be sure they get closer? Why couldn’t taking more terms cause the approximation to get worse, not better? 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.

5Important Definitions

We define a stream to have the following type:
 data Stream: | lz-link(first :: T, rest :: (-> Stream)) end

Streams are made up of closures. These are an opaque data structure: you can’t query their parts. The only thing you can do is run them. It is therefore useful to have a procedure that can examine finite prefixes of streams. Write a function that, given a Stream, extracts its finite prefix of the specified size, as a list:

 take :: Stream, Number -> List

Since you’ll need to use take to get the value of the first few elements of a stream, it is very important that your take function work correctly, since you’ll need to use it to write test cases for the other functions in this assignment!

You are allowed access to the following functions in the support code:

6Assignment: 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 -> Stream

For instance,
 take(repeating-stream([list: 1, 2, 3]), 8) is [list: 1, 2, 3, 1, 2, 3, 1, 2]

Also define
 cf-phi :: Stream cf-e :: Stream
that represent the streams of coefficients for $$\phi$$ and $$e$$, respectively (the definitions are given on Wikipedia).

Write a function that consumes a stream of coefficients and produces a corresponding stream of approximations:
 fraction-stream :: Stream -> Stream

To extract useful approximations, we must provide a threshold. When the absolute difference between a term in the stream of approximations and the next term in that stream is strictly below that threshold, we report the earlier term as the approximation:
 threshold :: Stream, Number -> Number
Assume that the first argument is the stream of approximations (not of coefficients). You can assume the threshold is chosen such that there is guaranteed to be an answer.

7Assignment: 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>>. As in Assignment: Part 1: Infinite Sequences, you can assume a non-empty input.

Define a function that converts a list of numbers into a corresponding stream of number options followed by nones:
 terminating-stream :: List -> Stream>
Now redefine all the previous functions to work over Stream<Option<Number>> instead:
 repeating-stream-opt :: List -> Stream> fraction-stream-opt :: Stream> -> Stream> threshold-opt :: Stream>, Number -> Number
Note that we may run out of values before finding an approximation within the desired threshold. If this happens, threshold-opt should raise the error "Threshold too small to approximate". Also convert
 cf-phi-opt :: Stream> cf-e-opt :: Stream>
(these should not have any nones) and finally, define at least five coefficients of the continued fraction of $$\pi$$:
 cf-pi-opt :: Stream>
What are the first five approximations? You may answer this question by writing a test for it.

8Analysis

Please analyze the big-O complexity of repeating-stream, fraction-stream, threshold, terminating-stream, repeating-stream-opt, fraction-stream-opt, and threshold-opt. What are the meaningful parameter(s) for your analysis? Please submit your analysis in PDF on the handin form (you can use any system you want, including Word, to generate the PDF).

Template