12,396,230 members (66,685 online)
Add your own
alternative version

17.7K views
262 downloads
13 bookmarked
Posted

# Fun with continued fractions

, 26 Sep 2012 CPOL
 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:

And some description from Barrow's web site:

Some other websites that are useful:

## License

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

## About the Author

 Engineer 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

 First Prev Next
 What do you mean by accurate to the 30,000 digit. Pascal Ganaye26-Sep-12 3:38 Pascal Ganaye 26-Sep-12 3:38
 Re: What do you mean by accurate to the 30,000 digit. Kenneth Haugland26-Sep-12 3:50 Kenneth Haugland 26-Sep-12 3:50
 Re: What do you mean by accurate to the 30,000 digit. Andreas Gieriet27-Sep-12 10:19 Andreas Gieriet 27-Sep-12 10:19
 Re: What do you mean by accurate to the 30,000 digit. Kenneth Haugland27-Sep-12 10:58 Kenneth Haugland 27-Sep-12 10:58
 Re: What do you mean by accurate to the 30,000 digit. Andreas Gieriet27-Sep-12 11:23 Andreas Gieriet 27-Sep-12 11:23
 Re: What do you mean by accurate to the 30,000 digit. Kenneth Haugland26-Sep-12 4:07 Kenneth Haugland 26-Sep-12 4:07
 Re: What do you mean by accurate to the 30,000 digit. Pascal Ganaye26-Sep-12 21:42 Pascal Ganaye 26-Sep-12 21:42
 Re: What do you mean by accurate to the 30,000 digit. Kenneth Haugland26-Sep-12 21:46 Kenneth Haugland 26-Sep-12 21:46
 My 5! Andreas Gieriet3-Sep-12 13:30 Andreas Gieriet 3-Sep-12 13:30
 Re: My 5! Kenneth Haugland3-Sep-12 13:58 Kenneth Haugland 3-Sep-12 13:58
 Thanks Andi Yes, I just watched the video in the referances and though I do it for the fun of it.
 Thank you! woutercx21-Jul-12 11:01 woutercx 21-Jul-12 11:01
 Re: Thank you! Kenneth Haugland21-Jul-12 11:22 Kenneth Haugland 21-Jul-12 11:22
 Re: Thank you! Kenneth Haugland22-Jul-12 2:27 Kenneth Haugland 22-Jul-12 2:27
 Re: Thank you! woutercx22-Jul-12 2:33 woutercx 22-Jul-12 2:33
 Re: Thank you! Kenneth Haugland22-Jul-12 2:35 Kenneth Haugland 22-Jul-12 2:35
 Re: Thank you! woutercx22-Jul-12 3:06 woutercx 22-Jul-12 3:06
 Re: Thank you! Kenneth Haugland22-Jul-12 3:39 Kenneth Haugland 22-Jul-12 3:39
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Jul-16 15:58 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.160721.1 | Last Updated 27 Sep 2012
Article Copyright 2012 by Kenneth Haugland
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid