Andrew Que Sites list Photos
Projects Contact
   I detest Power Point.  This is a typical slide in my Linear Algebra class.  The professor lectures and write over top of power point slides for 50 minutes a day.  If it doesn't look like it makes sense, it's because it doesn't.  This class really makes me respect my other math professors.
   Assisting Angela with a little Calc 2 work.  The series work in calculus seems to really get people, but to be honest it was one of my favorite sections.  I especially liked Taylor series.  What does that say about me?

April 24, 2011

Continued Fractions

So how does one convert a floating-point number to a rational number? For example, 0.25 = 1/4. The answer to this lays with continued fractions, and I will share an algorithm I learned.

One method that seems like it should work just fine is to multiply the fraction up to an integer number. For example, 0.01 can be multiplied up by 100 to form the fraction 1/100. Since there is a limit to integer sizes, an even power of two seems like it should work well. For example, 0.75 * 256 = 192, so the fraction is 192/256. This just needs to be reduced. Divide top and bottom by the GCD, 64, and the result is 3/4—exactly what we would expect.

Since the fractions are limited by the integers that represent it, one may as well multiply up by the largest integer number there is. For example, for signed 32-bit integers that number is 2,147,483,648. Here is the relationship:

Where n is the number of positive integer bits. This will work for any any number less then 1. For numbers greater then one, we just to the reverse:

In theory this system should work great. In practice, however, rounding errors show up because of the floating-point numbers. For example, using 16-bit integers, and 32-bit floating-point, the number 0.75 results in the fraction 24575/32767, which is actually 0.749992370372631···. So the simple approach isn't going to work.

Let us start with 0.25. In this case, we can simply invert the number. 1/0.25 = 4. Notice this relationship...



We have just found the ration representation of 0.25. But that only works if there is a value is of the form 1/n. Let us now try finding the rational form of 0.3. We'll start as we did last time 1/0.3 = 3.333. This says that:

But that isn't a rational number. What we can do is subdivide this down...

Now we can try and deal with the irrational part 0.333...

Substitute that back into our original equation and...

Reduce this down...

So 3/10=0.3—and that makes perfect sense.

There is a pattern forming, and the pattern is:


These are continued fractions. If we run long enough, we will find a solution for any rational number expressed in decimal form. Purely irrational numbers, such as π and e, will have an infinite number of terms.

We still need to go from placing the number into an infinite series to putting it into a rational number. Consider a general form for that used on 0.3.

Adding an other term:


One more time:

There is a pattern showing up, and I will break it down further so it becomes a little more apparent.

Notice how there is this basic pattern: a b + c. As the pattern progresses, b becomes the previous term, and c will split into an a b + c form. Let's break it down going the other direction:

This pattern has one additional fetcher: b is actually the previous a, and d is the previous c.

Each term is actually based on previous terms. In fact, it turns out that a history of the previous two results is all that is needed for each the numerator and denominator.

for the numerator.

for the denominator.

Where denotes truncation, or floor, or the integer part.

For an example, here is a break down of 2.432

i vi ai ni di
0     0 1
1     1 0
2 2.432 2 2 1
3 2.31481 2 5 2
4 3.18 3 17 7
5 5.67 5 90 37
6 1.5 1 107 44
7 2 2 304 125

So the result is 304/125, which is 2.432. This system works great for any rational number up until the limits of floating-point number (of which double precision can hold about 16 digits), and the integers used (32-bit signed integers are good for +/- 2 billion). While the system can come up with a rational approximate of irrational numbers, such as π, I don't know that they would be too useful. In rational form, numerator and denominators are as large as they can be without overflowing the integers they are in. So not much manipulation can be done without risking overflow.

I learned this method from code written by David Eppstein of the University of California, Irvine. It took me a while to understand the method, and be able to manipulate the implementation. But I think it's pretty clever, and very useful.