Converting a floating-point decimal value to a fraction

Question

Given a decimal floating-point value, how can you find its fractional equivalent/approximation? For example:

as_fraction(0.1) -> 1/10
as_fraction(0.333333) -> 1/3
as_fraction(514.0/37.0) -> 514/37

Is there a general algorithm that can convert a decimal number to fractional form? How can this be implemented simply and efficiently in C++?

Answer 1

First get the fractional part and then take the gcd. Use the Euclidean algorithm http://en.wikipedia.org/wiki/Euclidean_algorithm

void foo(double input)
{
    double integral = std::floor(input);
    double frac = input - integral;

    const long precision = 1000000000; // This is the accuracy.

    long gcd_ = gcd(round(frac * precision), precision);

    long denominator = precision / gcd_;
    long numerator = round(frac * precision) / gcd_;

    std::cout << integral << " + ";
    std::cout << numerator << " / " << denominator << std::endl;
}

long gcd(long a, long b)
{
    if (a == 0)
        return b;
    else if (b == 0)
        return a;

    if (a < b)
        return gcd(a, b % a);
    else
        return gcd(b, a % b);
}