Continued Fractions

by Stephen R. Schmitt

Contents

1. About
   
2. The source code
   
3. Discussion
   

1. About

This Java Script calculator computes the partial quotients and convergents of simple continued fractions. It was adapted from a BASIC program from the Astronomical Computing column of Sky & Telescope, January 1989.

The program is operated by entering a number and then pressing the Calculate button. A new browser window will open that lists the results of the computation. You may copy numbers from the Microsoft Windows calculator accessory into this Java Script calculator.

Return to Contents

2. The source code

The Java Script source code for this program can be viewed by using the View|Source command of your web browser.

You may use or modify this source code in any way you find useful, provided that you agree that the author has no warranty, obligations or liability. You must determine the suitablility of this source code for your use.

Return to Contents

3. Discussion

This calculator computes the partial quotients and convergents of simple continued fractions. These express a number x as

                    1
x = a0 + -----------------------
                      1
         a1 + ------------------
                        1
              a2 + -------------
                   a3 + ...

x = [a0, a1, a2, a3,...]

The algorithm for computing the terms a_n is as follows. Starting the indexing with i = 0,

r0 = x
a0 = floor( r0 )

r1 = 1 / (r0 - a0)
a1 = floor( r1 )

r2 = 1 / (r1 - a1)
a2 = floor( r2 )

and so on

The function floor(x) returns the largest integer less than or equal to x. The terms a_i are called partial quotients. Evaluating the continued fraction for the first i partial quotients results a quantity called the i^th convergent

ci = [a0, a1,..., ai]  

The convergents can be represented as the ratio of two integers:

ci = ni/di

The values of the numerator n and denominator d are computed using the following recursion. Starting from:

n-1 = 1 
d-1 = 0

n0 = a0 = floor( x )
d0 = 1

the next terms can be computed as follows

n1 = a1 n0 + n-1
d1 = a1 d0 + d-1

n2 = a2 n1 + n0
d2 = a2 d1 + d0

and so on

where the terms a_i are found as shown above.

Continued fractions are mainly used in number theory. They can provide a series of better and better rational approximations for irrational numbers. Continued fractions are also used in astronomy for finding near proportionalities between events with different time periods.

Return to Contents