Representing arbitrary fractions as rational expressions.

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

  1. qWake

    qWake Guest

    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
    qWake, May 24, 2004
    1. Advertisements

  2. qWake

    Ken Pledger Guest

    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
    part, leads to

    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

    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.


    Ken Pledger.
    Ken Pledger, May 24, 2004
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.