How can i format a decimal to a fraction with limits to the denominator

Question

Hi All I am trying to format a decimal A into a fraction B + C/D, where certain limit is imposed on D, say D could be one among [2...9] or [2...19] etc. BCD are integers The goal is to get the formatted fraction as close to the decimal as possible. Is there an existing algorithm/theory on this? Or is there any API I can call on Mac SDK?

Answer 1

Look into continued fractions.

Answer 2

// Not tested or even compiled :-). Assumes you are handling sign
// in:  a - the decimal to convert
//      limit - the largest denominator you will allow
// out: outN - Numerator
//      outD   Denominator

#include <math.h>

void d2f(double a, int limit, int& outN, int& outD) {
    double z;
    int dPrev, d, n;
    a = fabs(a);
    z = a;
    d = 1;
    n = a;
    dPrev = 0;
    while (a - (double)(n/d) != 0 && z != floor(z)) {
        z = 1 / (z - floor(z));
        int tmp = d;
        d = d * (int)floor(z) + dPrev;
        if (d > limit) {
            d = tmp;
            break;
        }
        dPrev = tmp;
        n = floor(a * d + 0.5);
    }
    outN = n;
    outD = d;
}

Hope that helps/works :-)