Here, we will present another way of approximating real numbers. To be more specific, we will deal with finite continued fractions only in this post.
is an example of a well-known irrational number. Some of its famous approximations are or . Where do these numbers come from?
Definition: A finite continued fraction (FCF) is any fraction of the form
where . We denote this by . A FCF is called pure, if all the coefficients are integers. For our purposes it is sufficient to restrict our attention to pure FCFs.
There also exist infinite continued fractions, which we will deal with in the next post. For example, continued fraction of is infinite, and it looks like .
Theorem: A continued fraction of is finite if and only if .
Given a FCF, how do we the corresponding rational number? Well, this is very easy. Let’s explore this in the following example.
Example: What is equal to? By definition, it it equal to
Exercise: Try doing the same thing and prove that and .
How about the inverse process? For a given rational, how do we determine a FCF? The algorithm works with the floor function and can be formulated as follows:
Output: a FCF for
Repeat: ; if then end else
Example: We will find a FCF for . First of all, we have that for some . What is the value of ? We see that , hence . So, for some . Similarly, , therefore . It follows that for some which is given by , hence, and we conclude that
Exercise: Find a FCF for and .
Remark: A FCF is determined “almost uniqely” by . The only small detail is as follows: if
then we can also write
If we insist on the last coefficient to be strictly greater than , then the expression of is unique.