Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / Visual Basic

Fun with continued fractions

Rate me:
Please Sign up or sign in to vote.
4.83/5 (8 votes)
26 Sep 2012CPOL5 min read 42.4K   387   14   17
Illustrates the calculation and the usefulness of continued fractions

Image 1

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.      

Image 2

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:     

Image 3       

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: 

VB
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)


Written By
Chief Technology Officer
Norway Norway
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWhat do you mean by accurate to the 30,000 digit. Pin
Pascal Ganaye26-Sep-12 3:38
Pascal Ganaye26-Sep-12 3:38 
AnswerRe: What do you mean by accurate to the 30,000 digit. Pin
Kenneth Haugland26-Sep-12 3:50
mvaKenneth Haugland26-Sep-12 3:50 
GeneralRe: What do you mean by accurate to the 30,000 digit. Pin
Andreas Gieriet27-Sep-12 10:19
professionalAndreas Gieriet27-Sep-12 10:19 
GeneralRe: What do you mean by accurate to the 30,000 digit. Pin
Kenneth Haugland27-Sep-12 10:58
mvaKenneth Haugland27-Sep-12 10:58 
GeneralRe: What do you mean by accurate to the 30,000 digit. Pin
Andreas Gieriet27-Sep-12 11:23
professionalAndreas Gieriet27-Sep-12 11:23 
AnswerRe: What do you mean by accurate to the 30,000 digit. Pin
Kenneth Haugland26-Sep-12 4:07
mvaKenneth Haugland26-Sep-12 4:07 
GeneralRe: What do you mean by accurate to the 30,000 digit. Pin
Pascal Ganaye26-Sep-12 21:42
Pascal Ganaye26-Sep-12 21:42 
GeneralRe: What do you mean by accurate to the 30,000 digit. Pin
Kenneth Haugland26-Sep-12 21:46
mvaKenneth Haugland26-Sep-12 21:46 
Dosnt make any sence to me, what would the relation number be, the number of fraction? The number inside the fraction? Confused | :confused:
GeneralMy 5! Pin
Andreas Gieriet3-Sep-12 13:30
professionalAndreas Gieriet3-Sep-12 13:30 
GeneralRe: My 5! Pin
Kenneth Haugland3-Sep-12 13:58
mvaKenneth Haugland3-Sep-12 13:58 
GeneralThank you! Pin
woutercx21-Jul-12 11:01
woutercx21-Jul-12 11:01 
GeneralRe: Thank you! Pin
Kenneth Haugland21-Jul-12 11:22
mvaKenneth Haugland21-Jul-12 11:22 
GeneralRe: Thank you! Pin
Kenneth Haugland22-Jul-12 2:27
mvaKenneth Haugland22-Jul-12 2:27 
GeneralRe: Thank you! Pin
woutercx22-Jul-12 2:33
woutercx22-Jul-12 2:33 
GeneralRe: Thank you! Pin
Kenneth Haugland22-Jul-12 2:35
mvaKenneth Haugland22-Jul-12 2:35 
GeneralRe: Thank you! Pin
woutercx22-Jul-12 3:06
woutercx22-Jul-12 3:06 
GeneralRe: Thank you! Pin
Kenneth Haugland22-Jul-12 3:39
mvaKenneth Haugland22-Jul-12 3:39 

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

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