# Representing arbitrary fractions as rational expressions.

Discussion in 'Undergraduate Math' started by qWake, May 24, 2004.

1. ### qWakeGuest

I wrote a program (in C++) to express an arbitrary fraction as a rational
expression that best approximates its value. It finds the most accurate
denominator using an accessory function that takes two parameters:
1 - a "double" containing the fraction to represent (eg 0.123456789)
2 - an "unsigned int" for the highest acceptable denominator (eg 10000) to
set the desired precision of the rational estimate.

The function will return denominator 81 given parameters 0.123456789 and
10000, so the numerator is directly calculated to be 10 and the program
writes 10/81. Fine so far.

The problem is that the program is naive: it works by testing all possible
denominators from 2 to 10000 (or other limit), checking the margin of error
in each case and returning the denominator that produces the lowest error.
If I want to increase the accuracy of the rational expression to get ten
digits (second parameter = 9,999,999,999) so that the program outputs
123456789/1000000000 then the program's running time becomes unacceptably
long as it checks millions of possible denominators.

The question is: does a faster method exist to determine the best (most
accurate) denominator that can be used to express a fraction?

Even if you don't have an answer, hints as to where to start looking are
welcome.

qWake, May 24, 2004

2. ### Ken PledgerGuest

Continued fractions.

As a simple example, here's how to find a simple fraction
aprroximating 0.835. Of course it's exactly 167/200, but you might
want an approximation with smaller numerator and denominator.

Repeatedly taking the reciprocal and then subtracting the integer

0.835 = 1/(1 + 1/(5 + 1/(16 + 1/2))).

When a reasonably large number turns up, try neglecting its reciprocal.
In this example 16 is noticeably large, so 1/16 is a lot smaller than 5.
That suggests the approximation

1/(1 + 1/5) = 5/6, which you can see is pretty close to 0.835.

A well-known example is pi, whose infinitely continued fraction
begins

pi = 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + ......)))).

Neglecting 1/15 gives the well-known approximation 3 + 1/7 = 22/7.
Neglecting the smaller number 1/292 gives the much better
approximation 3 + 1/(7 + 1/(15 + 1/1)) = 355/113.

HTH

Ken Pledger.

Ken Pledger, May 24, 2004