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 Theme Song
Unwritten by Natasha Bedingfield
3 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.
4 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 (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.
5 Important Definitions
data Stream<T>:
| lz-link(first :: T, rest :: (-> Stream<T>))
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<T> :: Stream<T>, Number -> List<T>
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!
6 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>
take(repeating-stream([list: 1, 2, 3]), 8)
is [list: 1, 2, 3, 1, 2, 3, 1, 2]
cf-phi :: Stream<Number>
cf-e :: Stream<Number>
fraction-stream :: Stream<Number> -> Stream<Number>
threshold :: Stream<Number>, Number -> Number
7 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—
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>>.
terminating-stream :: List<Number> -> Stream<Option<Number>>
repeating-stream-opt :: List<Number> -> Stream<Option<Number>>
fraction-stream-opt :: Stream<Option<Number>> -> Stream<Option<Number>>
threshold-opt :: Stream<Option<Number>>, Number -> Number
cf-phi-opt :: Stream<Option<Number>>
cf-e-opt :: Stream<Option<Number>>
cf-pi-opt :: Stream<Option<Number>>
8 Analysis
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).