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);
}

Answer 2

#include <iostream>
#include <valarray> 

using namespace std;

void as_fraction(double number, int cycles = 10, double precision = 5e-4){
    int sign  = number > 0 ? 1 : -1;
    number = number * sign; //abs(number);
    double new_number,whole_part;
    double decimal_part =  number - (int)number;
    int counter = 0;
    
    valarray<double> vec_1{double((int) number), 1}, vec_2{1,0}, temporary;
    
    while(decimal_part > precision & counter < cycles){
        new_number = 1 / decimal_part;
        whole_part = (int) new_number;
        
        temporary = vec_1;
        vec_1 = whole_part * vec_1 + vec_2;
        vec_2 = temporary;
        
        decimal_part = new_number - whole_part;
        counter += 1;
    }
    cout<<"x: "<< number <<"\tFraction: " << sign * vec_1[0]<<'/'<< vec_1[1]<<endl;
}

int main()
{
    as_fraction(3.142857);
    as_fraction(0.1);
    as_fraction(0.333333);
    as_fraction(514.0/37.0);
    as_fraction(1.17171717);
    as_fraction(-1.17);
}


x: 3.14286      Fraction: 22/7                                                                                                                
x: 0.1          Fraction: 1/10                                                                                                                        
x: 0.333333     Fraction: 1/3                                                                                                                 
x: 13.8919      Fraction: 514/37                                                                                                              
x: 1.17172      Fraction: 116/99                                                                                                              
x: 1.17         Fraction: -117/100

Sometimes you would want to approximate the decimal, without needing the equivalence. Eg pi=3.14159 is approximated as 22/7 or 355/113. We could use the cycles argument to obtain these:

as_fraction(3.14159, 1);
as_fraction(3.14159, 2);
as_fraction(3.14159, 3);

x: 3.14159      Fraction: 22/7                                                                                                                
x: 3.14159      Fraction: 333/106                                                                                                             
x: 3.14159      Fraction: 355/113

Answer 3

(Too long for a comment.)

Some comments claim that this is not possible. But I am of a contrary opinion.

I am of the opinion that it is possible in the right interpretation, but it is too easy to misstate the question or misunderstand the answer.

The question posed here is to find rational approximation(s) to a given floating point value.

This is certainly possible since floating point formats used in C++ can only store rational values, most often in the form of sign/mantissa/exponent. Taking IEEE-754 single precision format as an example (to keep the numbers simpler), 0.333 is stored as 1499698695241728 * 2^(-52). That is equivalent to the fraction 1499698695241728 / 2^52 whose convergents provide increasingly accurate approximations, all the way up to the original value: 1/3, 333/1000, 77590/233003, 5586813/16777216.

Two points of note here.

• For a variable float x = 0.333; the best rational approximation is not necessarily 333 / 1000, since the stored value is not exactly 0.333 but rather 0.333000004291534423828125 because of the limited precision of the internal representation of floating points.

• Once assigned, a floating point value has no memory of where it came from, or whether the source code had it defined as float x = 0.333; vs. float x = 0.333000004; because both of those values have the same internal representation. This is why the (related, but different) problem of separating a string representation of a number (for example, a user-entered value) into integer and fractional parts cannot be solved by first converting to floating point then running floating point calculations on the converted value.

---

[ EDIT ]   Following is the step-by-step detail of the 0.333f example.

1. The code to convert a float to an exact fraction.

#include <cfloat>
#include <cmath>
#include <limits>
#include <iostream>
#include <iomanip>

void flo2frac(float val, unsigned long long* num, unsigned long long* den, int* pwr)
{
    float mul = std::powf(FLT_RADIX, FLT_MANT_DIG);
    *den = (unsigned long long)mul;
    *num = (unsigned long long)(std::frexp(val, pwr) * mul);
    pwr -= FLT_MANT_DIG;
}

void cout_flo2frac(float val)
{
    unsigned long long num, den; int pwr;
    flo2frac(val, &num, &den, &pwr);

    std::cout.precision(std::numeric_limits<float>::max_digits10);
    std::cout << val << " = " << num << " / " << den << " * " << FLT_RADIX << "^(" << pwr << ")" << std::endl;
}

int main()
{
    cout_flo2frac(0.333f);
}

2. Output.

0.333000004 = 11173626 / 16777216 * 2^(-1)

3. This gives the rational representation of float val = 0.333f; as 5586813/16777216.

4. What remains to be done is determine the convergents of the exact fraction, which can be done using integer calculations, only. The end result is (courtesy WA):

0, 1/3, 333/1000, 77590/233003, 5586813/16777216

Answer 4

I came up with an algorithm for this problem, but I think it is too lengthy and can be accomplished with less lines of code. Sorry about the poor indentation it is hard trying to align everything on overflow.

#include <iostream>
using namespace std;


// converts the string half of the inputed decimal number into numerical values void converting
 (string decimalNumber, float&numerator, float& denominator )

 { float number; string valueAfterPoint =decimalNumber.substr(decimalNumber.find("."    ((decimalNumber.length() -1) )); // store the value after the decimal into a valueAfterPoint 

int length = valueAfterPoint.length(); //stores the length of the value after the decimal point into length 

numerator = atof(valueAfterPoint.c_str()); // converts the string type decimal number into a float value and stores it into the numerator

// loop increases the decimal value of the numerator by multiples of ten as long as the length is above zero of the decimal

for (; length > 0; length--)  
    numerator *= 10;

do
 denominator *=10;
  while  (denominator < numerator);



// simplifies the the converted values of the numerator and denominator into simpler values for          an easier to read output 


void simplifying (float& numerator, float& denominator) { int maximumNumber = 9; //Numbers in the tenths place can only range from zero to nine so the maximum number for a position in a position for the decimal number will be nine

bool isDivisble; // is used as a checker to verify whether the value of the numerator has the       found the dividing number that will a value of zero
 // Will check to see if the numerator divided denominator is will equal to zero


   if(int(numerator) % int(denominator) == 0) {
   numerator /= denominator;
   denominator = 1;   
   return; }


  //check to see if the maximum number is greater than the denominator to simplify to lowest     form while (maximumNumber < denominator) { maximumNumber *=10;  }


 // the maximum number loops from nine to zero. This conditions stops if the function isDivisible is true 
 for(; maximumNumber > 0;maximumNumber --){

 isDivisble = ((int(numerator) % maximumNumber == 0) && int(denominator)% maximumNumber == 0);

  if(isDivisble)
 {
    numerator /= maximumNumber;  // when is divisible true numerator be devided by the max        number value for example 25/5 = numerator = 5

   denominator /= maximumNumber; //// when is divisible true denominator be devided by themax        number value for example 100/5 = denominator = 20

 }


 // stop value if numerator and denominator is lower than 17 than it is at the lowest value
 int stop = numerator + denominator;

 if (stop < 17)
 {
     return;
 } } }   

Answer 5

#include<iostream>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>

/*
May be over done but seems to work as far as I have tested. 
Convert a decimal to a fraction or mixed number.
write a function that derives the number of decimal places by multipling
the fractional part by powers of 10 until no fractional part is left
maybe check using a \bool is_fraction()\ function that returns true or false
and a recursive function to multiply powers of 10 , to derive the numerator by 
moving the decimal place:
the denominator is the power of ten that leaves no fractional parts.
use the solutions to generate a fraction then if needed reduce it(maybe a 
function 
that finds the greatest common divisor).
if it reduces to a numerator over 1 print just the whole number integer.
remember to catch divide by zero, and irrational numbers should be rounded and
displayed as approx values.
*/

struct Fraction {
    double value{0.0}; // The initial value entered
}; Fraction F;

class fraction {
private:
    double decimal{}; // The decimal part
    int whole{};   // The whole number part
    int numerator{}; 
    int denominator{};


public:
    fraction() {} // default constructor
   // This does the conversion, calls all the help
    void get_fraction(double& n) {         
        F.value = n;
        set_whole_part(F.value);
        set_fraction_part(F.value);
        set_numerator();
    }
    // This provides the help
    double set_fraction_part(const double& );
    double set_whole_part(const double& );
    double get_f_part();
    double get_w_part();
    double set_numerator();
    int set_denominator(unsigned&);
    int get_denominator(){ return denominator; }
    double get_numerator() { return numerator; }
    int GCD(int numer, int denom);
    bool is_numerator(double&);
    double number{}; // bool number 0.99999999
    // output operator
    friend std::ostream& operator<<(std::ostream& os, fraction& f); 
    // input operator
    friend std::istream& operator>>(std::istream& is, fraction& f);
   
};
double fraction::set_whole_part(const double& )
{
    double w_part = F.value; // whole number part
    return whole = static_cast<int>(w_part); // return an integer value
}
double fraction::set_fraction_part(const double&)
{
    double f_part = F.value; // fractional number part
 // returns the fractional component of float or double
    return decimal = modf(F.value, &f_part);  

}
double fraction::get_f_part()
{
    return decimal; // decimal part
}
double fraction::get_w_part()
{
    return whole;
}
// istream operator 
std::istream& operator>>(std::istream& is, fraction& f) {
    double n = 0.0;
    is >> n;
    f.get_fraction(n);
    return is;
}
// ostream operator has friend status so can access private members

std::ostream& operator<<(std::ostream& os, fraction& f)
{
    os << static_cast<double>(f.numerator)/f.denominator << '\n';
    if (f.numerator == 0 && f.denominator == 1) {
        f.numerator = (f.whole);
    }
    if (f.whole >= 1 && f.numerator != 0 && f.denominator != 0) {
        os << f.whole<<' ' << f.numerator << '/' << f.denominator << '\n';
        return os;
    }
    if (f.whole == 0 && f.numerator != 0 && f.denominator != 0) {
        os << f.numerator << '/' << f.denominator << '\n';
        return os;
    }
    if (f.numerator == 0 && f.denominator == 0) {
        os << f.whole << '\n';
        return os;
    }
        os << "failed to create numerator/denominator\n";
        return os;
}
// returns the greatest common divisor
int fraction::GCD(int numer, int denom) {
    return denom > 1 ? GCD(denom, numer % denom) : numer;
}
bool fraction::is_numerator(double& n)
{
//using the rounding information to create the break point.
//This will lose information on the original value stored.
//is the least significant digit being rounded toward zero or one?
    if (n <= 0.00000001) { number = 0.00000000; return false; }   // dont't round
    if (n <= 0.99999999) { number = 0.99999999; return true; } // round up

    return false;
}
int fraction::set_denominator(unsigned& denom)
{
    return denominator = denom;
}
double fraction::set_numerator() 
{
    double num = get_f_part();
    double dec = 0.0;
    unsigned count = 0;
    double f_part = 0;

    while (is_numerator(num) == true) 
    {
        num *= 10; // move one decimal place and count
        f_part = num; // make a new double.decimal 
        double dec = modf(num, &f_part); // get the new decimal part
    
        num = dec; // re-initialize
    
        ++count; // keeps count of shifts of fractional part
    }
    unsigned exp = 1; // exponenent = power of 10
    for (unsigned i = 0; i < count;  ++i) {
        exp *= 10; // get the total shifts of decimal point
    }
    //promote exp to avoid  arithmatic over flow
    double s_dec = decimal * static_cast<double>(exp);
    // cast back to an int  for GCD(returns an int)
    int n_dec = static_cast<int>(s_dec);    
    if (number == 0.999999) {
        n_dec += 1; // round up
    }
if ((whole != 0) && (number == 0.99999999)) {
    // if rounding toward one than add one.(the bool discarded that info).
    n_dec += 1;
}
    unsigned reduced = GCD(n_dec, exp); // find Greatest Common Divisor 
    if (reduced <= 0) { // no common divisor return as is
    
        set_denominator(exp);
        return numerator = n_dec; // may produce a zero numerator
        std::cerr << "could not convert fraction\n";
    }
    else if (reduced >= 1) { // reduce the fraction
        unsigned denom = exp / reduced;
        denominator=denom;
        unsigned numer = n_dec / reduced;
        return numerator = numer;
    }
    else
        std::cerr << "could not convert fraction\n";

    return 0;
}

 int main()
{
    fraction f;
    for (fraction ff; std::cin >> std::setprecision(12) >> std::fixed >> f;)
        std::cout << f;
        return 0;
}

Answer 6

I agree completely with dxiv's solution but I needed a more general function (I threw in the signed stuff for fun because my use cases only included positive values):

#include <concepts>
template <std::integral Tout, std::floating_point Tin>
auto to_fraction(Tin f) -> std::tuple<Tout, Tout>
{
    // may need to be "const" instead of "constexpr" depending on library
    constexpr Tin multiplier
    {
        std::pow(std::numeric_limits<Tin>::radix, std::numeric_limits<Tin>::digits)
    };
    uint64_t denominator{ static_cast<uint64_t>(multiplier) };
    int power;
    int64_t numerator{ static_cast<int64_t>(std::frexp(f, &power) * multiplier) };
    uint64_t factor
    {
        static_cast<uint64_t>(
            std::pow(std::numeric_limits<Tin>::radix, std::abs(power)))
    };
    if (power > 0)
    {
        numerator *= factor;
    }
    else
    {
        denominator *= factor;
    }

    Tout num_fix {1};
    if constexpr(std::is_signed_v<Tout>)
    {
        num_fix = numerator < 0 ? -1 : 1;
        numerator = std::abs(numerator);
    }

    // get the results into the requested sized integrals.
    while((numerator > std::numeric_limits<Tout>::max() 
           || denominator > std::numeric_limits<Tout>::max()) 
          && denominator > 1)
    {
        numerator >>= 1;
        denominator >>= 1;
    }

    return 
    {
        num_fix * static_cast<Tout>(numerator),
        static_cast<Tout>(denominator)
    };
};

You can call this like:

auto [n, d] { to_fraction<int8_t>(-124.777f) };

And you get n=-124, d=1;

auto [n, d] { to_fraction<uint64_t>(.33333333333333) };

gives n=6004799503160601, d=18014398509481984