Click here to Skip to main content
Click here to Skip to main content

Fun with continued fractions

, 26 Sep 2012
Rate this:
Please Sign up or sign in to vote.
Illustrates the calculation and the usefulness of continued fractions

Introduction   

Continued fractions are of great importance in many aspects, as they have many implementations for real problems where you want to describe something with an approximate fraction, or you simply want to replace a decimal or double number with a fraction.   

Background         

As always in mathematics the history of continued fractions are quite complicated. The earliest traces of continued fractions appear as far back as 306 b.c. Other records have been found that show that the Indian mathematician Aryabhata used a continued fraction to solve a linear equation.

In the western hemisphere it did not appear until the 17th century, when William Brouncker and John Wallis started to formulate some form of continued fractions. The Dutch mathematician and astronomer, Christiaan Huygens made the first practical application of the theory in 1687, and wrote a paper explaining how to use convergents to achive the best rational approximations for gear ratios. These approximations enabled him to pick the gears with the best numbers of teeth as he was going to build a mechanical planetarium.   

Representation and calculations of continued fractions  

How to write a continued fraction anyway, well let's take the simple quadratic equation:    

x^2 - bx -1 = 0          

Move things over and divide by X and you can rewrite it like this:      

x = b + 1/x         

We realize that we have a formula for X on the left, and we have an X on the right side. We now substitute the X on the right side with the formula on the right. Sounds complicated, but here is the result with one substitution:        

x = b + 1/(b + 1/x)         

We can do this an infinite number of times and get a continued fraction. This is an interesting formula if we plug in b = 1 we would get the golden ration. (to get this number you simply type in (sqrt(5)-1)/2 in the program submitted).  

In the general representation of a continued fraction is given below, where x is a number (irrational or rational) and the coefficients a0, a1, and so on are all positive integers.      

The continued fraction is quite complicated to write in this way, so they are usually represented as a series of the coefficients as given below:     

       

Finite numbers would have a finite set of fractions, while irrational number (sqrt(2)) could be given a rational approximate representation if you adruptly stop it at one of the coefficients. This is called the n'th convergent of the continued fraction.       

To calculate the numbers an you should simply do this:  

a0 = Math.Floor(some decimal number)    

we must also store the rest of the number in the temporary variable b: 

b = some decimal number - Math.Floor(some decimal number)   

a1 = 1/(b)     

If we continue this, as shown in the code below, we would get all the expansions we desire: 

Private Function GetSeriesExpantion(ByVal input As Decimal, ByVal NrFraction As Integer) As Integer
    Dim intput As Decimal = input
    Dim temp_dec As Integer
    For i As Integer = 0 To NrFraction
        temp_dec = CInt(Math.Floor(intput))
        intput = intput - Math.Floor(intput)
        If Not intput = 0 Then
            intput = 1 / intput
        Else
            intput = 0
        End If
    Next
    Return temp_dec
End Function    

To get the resulting n'th convergent fraction I have designed an own fraction struct that can add a whole number to a fraction, and the result would be given below the an series in the program.  

Continued fractions in action       

Why go to all of this trouble? Well as it turns out continued fractions produces a much better
approximation then the 10 digit system (for instance 314/100 in the case of Pi). You should also notice that the fraction approximation is better, the sooner you get a large number in the An series. As a direct result of this, the worst case scenario would be an expansion were all the numbers (in the An series) is 1.  

An example were a series can be terminated at a hugh number is shown in the first program demo picture. The result was discovered by Ramanujan, who was an extraordenary natural talent in mathematics. He studied continued fractions and found, among other things, an approximate formula for pi written like this:    

pi = (2143/22)^(1/4)          

This is an accurate to the 8 digit after the decimal sign, and that really should be good enough for any practical use! To see why this approximation works so well, you should take a note of the example picture in the beginning of the article. It shows the continued expasion of the number pi^4 and as you can see the number a5 is over 16000, and if we cut the continued series expansion we would get the number in Ramanujan's approximate formula for pi.  

To summarize the uses of continued fractions: 

  • The scale models are can be created with small errors using the convergent  
  • They convert rather quickly in comparison to other techniques.       
  • We've seen that they have many computationally desirable properties
  • They represent all real numbers accurately    
  • They yield good approximations when truncated    
  • They're easy to compare   
  • They have no weird biases toward the number 10  

Why don't we see them used more often?  (I've seen other articles on the codeproject site that convert a decimal number to a fraction; this should also be done by using the continued fractions.) 

History  

The article with all the explanations is based heavily on the reference given below, and my contribution is quite small, as I only made the program that gives you the possibility to calculate them easily.    

The evaluator is simply the one I made previously for complex numbers, as I do not have the permission to publish the code with double taken from "Programming Microsoft Visual Basic .NET" (2003) - Francesco Balena (pages 505 - 509.). The evaluator should be replased with one that takes decimal numbers to get more accurate results.   

References       

There is an excellent video by Professor John Barrow on Continued Fractions available on fora.tv for free, if you like to know more be sure to check it out. Some of the material from this article is from the video by him:       

http://fora.tv/2010/11/16/Gresham_Professor_John_Barrow_Continued_Fractions   

And some description from Barrow's web site:     

http://plus.maths.org/content/chaos-numberland-secret-life-continued-fractions 

Some other websites that are useful:       

http://archives.math.utk.edu/articles/atuyl/confrac/     

http://en.wikipedia.org/wiki/Continued_fraction      

http://www-math.mit.edu/phase2/UJM/vol1/COLLIN~1.PDF 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Kenneth Haugland
Engineer
Norway Norway
I hope that you like the stuff I have created and if you do wish to say thank you then a donation is always appreciated.
You can donate here[^].

Comments and Discussions

 
QuestionWhat do you mean by accurate to the 30,000 digit. PinmemberPascal Ganaye26-Sep-12 3:38 
AnswerRe: What do you mean by accurate to the 30,000 digit. PinmemberKenneth Haugland26-Sep-12 3:50 
Not sure; from the website reference:
The remarkable Indian mathematician Srinivasa Ramanujan (1887-1920)was famous for his uncanny intuition about numbers and their inter-relationships. Like mathematicians of past centuries he was fond of striking formulae and would delight in revealing (apparently from nowhere) extraordinarily accurate approximations (can you show that $2^{10}\approx 10^3$ ?). Ramanujan was especially fond of cfes and had an intimate knowledge of their properties. Knowing this one can see how he arrived at some of his unusual approximation formulae. He knew that when some irrational number produced a very large quotient in the first few term of its cfe then it could be rationalised to produce an extremely accurate approximation to some irrational. A nice example is provided by Ramanujan’s approximation to the value of $\pi $,
\begin{equation} \pi \approx \left( \frac{2143}{22}\right) ^{\frac14} \end{equation} (16)
 
which is good to 3 parts in 10^4.
 
3 parts in 10^4 became 30 000, or Im I reading this wrong?
 
Your calculator would anyway produce roundoff errors while performing sqrt twice, but how much that comes into play Im not sure about.
GeneralRe: What do you mean by accurate to the 30,000 digit. PinmemberAndreas Gieriet27-Sep-12 10:19 
GeneralRe: What do you mean by accurate to the 30,000 digit. PinmemberKenneth Haugland27-Sep-12 10:58 
GeneralRe: What do you mean by accurate to the 30,000 digit. PinmemberAndreas Gieriet27-Sep-12 11:23 
AnswerRe: What do you mean by accurate to the 30,000 digit. [modified] PinmemberKenneth Haugland26-Sep-12 4:07 
GeneralRe: What do you mean by accurate to the 30,000 digit. PinmemberPascal Ganaye26-Sep-12 21:42 
GeneralRe: What do you mean by accurate to the 30,000 digit. PinmemberKenneth Haugland26-Sep-12 21:46 
GeneralMy 5! PinmemberAndreas Gieriet3-Sep-12 13:30 
GeneralRe: My 5! PinmemberKenneth Haugland3-Sep-12 13:58 
GeneralThank you! [modified] Pinmemberwoutercx21-Jul-12 11:01 
GeneralRe: Thank you! PinmemberKenneth Haugland21-Jul-12 11:22 
GeneralRe: Thank you! [modified] PinmemberKenneth Haugland22-Jul-12 2:27 
GeneralRe: Thank you! Pinmemberwoutercx22-Jul-12 2:33 
GeneralRe: Thank you! PinmemberKenneth Haugland22-Jul-12 2:35 
GeneralRe: Thank you! Pinmemberwoutercx22-Jul-12 3:06 
GeneralRe: Thank you! [modified] PinmemberKenneth Haugland22-Jul-12 3:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140721.1 | Last Updated 27 Sep 2012
Article Copyright 2012 by Kenneth Haugland
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid