Skip to main content
GameDev.net gamedev.net
🔒 Locked

How do I Convert a Decimal to a Fraction in c++?

Started by MasterDario Oct 26, 2005 at 2:46 PM 12 replies 27.4k views
Original Post
MasterDario
MasterDario
Hi how is everyone doing, im currently creating a c++ program in which I have a fraction class. In this class i want to create a method in which i can convert a decimal number such as 72.75 into a fraction 72 and 3/4, but im not sure how i would go about doing this so i was hoping for some help. Dario
n/a
Mantear
Mantear
Some more information could help. Is there a limit to how many decimal places you can have?
MasterDario
MasterDario
sorry about that, in the conversion i want it to assume that all numbers have a max of 3 decimal places.
n/a
Nairb
Nairb
Well, here's an idea, although probably not the best.

First, seperate the integer and decimal portion. This can be done like so:
float decimal = num - (int)num;
int integer = (int)num;

So in your case, now decimal has .75 and integer has 75.

Now multiply decimal by a reall big power of 10 (say 10^6) or something to make it not a decimal. Not that in the case of rounding errors, you might lose some precision. Ie: .75 * 1000000 = 750000.
750000/1000000 is your fraction.

Once you've gotten that far, you can find the greatest common denominator between 750000 and 1000000 and divide to reduce the fraction. I would suggest using Newton's method to find the gcd, as finding it iteratively for such big numbers would take a long time.

Edit: If you're assuming three decimal places, you can multiply by 1000 instead. Also, rounding errors might get in the way of you having an accurate fractional representation.

Hope that helps,
--Brian
stylin
stylin
Quote:
Original post by Mantear
Some more information could help. Is there a limit to how many decimal places you can have?

Strip the whole number to leave you with just the rational (decimal) part. Decide on a level of precision you'd like (tenths, hundreds, thousandths, etc.), multiply your decimal by that. Floor it and you'll now have a whole number representing the numerator of your fraction, with whatever precision as your denominator.

EDIT: beaten. ApochPiQ's method takes into account rational size and thus is a better solution (but may be somewhat slower since string manipulation is involved).
:stylin: "Make games, not war." "...if you're doing this to learn then just study a modern C++ compiler's implementation." -snk_kid
ApochPiQ
ApochPiQ
Well, the easiest way to do this would be to split the number at the decimal. Some rough pseudocode would look like this:

Find decimal point
If there is no decimal, just convert the input to an integer and return
Take everything to the left of the decimal and treat it as the integer portion
Take everything to the right and copy it into a separate string
Count the number of digits in the decimal portion of the number (e.g. 2 digits in 72.75)
Find 10^n (100 in this case)
Your root fraction is now decimal_portion/10^n, e.g. 75/100

From there it's just a matter of using a well-known greatest-common-factor algorithm to reduce the fraction, and you're all done. Implementing that should be fairly easy with std::string and either a stringstream or boost::lexical_cast.


[edit] Sheesh... take 5 minutes to write a post and the question is answered a dozen times already [razz]
MasterDario
MasterDario
thanks i got it to work
n/a
Extrarius
Extrarius
Here is a working version that doesn't bother with the iteration everybody else mentioned, minus the GCD algorithm that I couldn't be bothered to write:
#include <cmath>#include <limits>#include <algorithm>using namespace std;struct Fraction{   int WholePart;   int Numerator;   int Denominator;};//Precision controls how many digits after the decimal are keptbool DecimalToFraction(double DecimalNum, Fraction &Result){   const int MaxIntDigits = numeric_limits<int>::digits10;   const int WholeDigits = int(log10(DecimalNum));   const int FractionDigits = min(numeric_limits<double>::digits10 - WholeDigits, MaxIntDigits-1);   //If number has too many digits, can't convert   if(WholeDigits > MaxIntDigits)   {	   return false;   }   //Separate into whole part and fraction   double WholePart;   DecimalNum = modf(DecimalNum, &WholePart);   Result.WholePart = int(WholePart);   //Convert the decimal to a fraction   const double Denominator = pow(10.0, FractionDigits);   Result.Numerator = int((DecimalNum * Denominator) + 0.5);   Result.Denominator = int(Denominator);   //Return success   return true;}double FractionToDecimal(Fraction &FractionNum){	const double WholePart = double(FractionNum.WholePart);	const double DecimalPart = double(FractionNum.Numerator) / double(FractionNum.Denominator);	return WholePart + DecimalPart;}
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
Agony
Agony
The problem with the suggested method is that you're limited to the denominator that you pick, or number that divide into it evenly. You'll never turn .333 into 1/3, for example. I wrote a function last summer that handles this problem a bit differently. You give it a number (I can't remember if it needs to be between 0.0 and 1.0 or not), and an acceptable error margin, and it will find the fraction with the smallest denominator that is within the error margin. I'll post the code, and try to figure out how it works again...
std::pair<long, long> SimplestFraction(double Value, double Error){  double Numerator = 0.0;    //Start with the fraction 0/1; it has the smallest positive denominator  double Denominator = 1.0;  //Keep the numerator and denominator as doubles                             //to avoid repeated conversion of long->double->long  double Delta0;  //These two deltas record the amount of error  double Delta1;  //that the current two fractions have  do  {    //We know that our number falls between Numerator/Denominator and (Numerator + 1)/Denominator    //Let's figure out the deltas, to find out which one is closer to our real value    Delta0 = abs(Value - Numerator / Denominator);    Delta1 = abs(Value - (Numerator + 1.0) / Denominator);    //If Delta0 is further from our real value, then we need to make some adjustments    if (Delta0 > Delta1)    {      //Increase the numerator by one, because we need a slightly larger fraction      //to keep up with the denominator increase      Numerator += 1.0;      //Set Delta0 to Delta1, since we'll use that value in the while loop      //below to see if we've found a sufficient fraction, and Delta1 was      //the smaller delta that we decided to go with      Delta0 = Delta1;    }    //Increase the denominator, because (unless we're good this time), we need to keep getting    //a larger denominator to find a more accurate fraction    Denominator += 1.0;  } while (Delta0 > Error);  //As long as our delta is too large, keep trying further  //We've gotten a sufficiently accurate fraction; return the numbers we found  //(reduce the denominator by one, because our last increase of the denominator was unneeded)  return std::pair<long, long>(long(Numerator), long(Denominator) - 1);}

So basically, at any stage of the process, you have two fractions. You know that one fraction is smaller than the real value, and one fraction is larger. You find out which one is more accurate, and then you go to the next higher denominator. You have to increment the numerator by one when you do this only if the larger fraction was more accurate. Otherwise, all you need to do is increase the denominator. Example:
0.5731, with an error of 0.01Fractions (lower and higher)    Deltas             Increment Numerator?----------------------------    ---------------    --------------------  0 /   1         1 /   1       0.5731   0.4269    Yes  1 /   2         2 /   2       0.0731   0.4269    No  1 /   3         2 /   3       0.2398   0.0936    Yes  2 /   4         3 /   4       0.0731   0.1769    No  2 /   5         3 /   5       0.1731   0.0269    Yes  3 /   6         4 /   6       0.0731   0.0936    No  3 /   7         4 /   7       0.1445   0.0017    Done!Result = 4/7 = 0.5714

(I just realized that the algorithm isn't perfect. In that last row, you'll notice that both 3/7 and 4/7 are below the real value, but I was assuming that it was guaranteed that the real value would be between the two fractions. Oh well. It always worked well for me anyway. Maybe it can be tweaked just a bit more.)

[edit]Also, the value does indeed need to be between 0.0 and 1.0. So you'll have to do a modf() or something similar like others have done to get the whole version. Then with the decimal portion separated, you can use this algorithm to get the fractional portion as a numerator/denominator.[/edit]
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o
Caitlin
Caitlin
You could find the fraction by using the decimal portion as the slope of a line originating at 0,0. All you need to do then is step through y values, divide x by y, round it to the desired precision, then compare it to your decimal. As soon as you step through all of your y values, you increment x and repeat the process through all the y values. Its slow but good if you are not looking for speed. It will also give you a reduced fraction by default, in fact it is the first fraction it comes across that matches your decimal when doing calculations.

It might look something like this:

DECIMAL = .75 'per your example

MAXDECIMALPLACES = 3 'just an example, you could have anything here you wanted

XMAXIMUM = 10 ^ MAXDECIMALPLACES 'here we have 1000 as our x maximum

X = 1
Y = 1

DO
IF Y = XMAXIMUM THEN 'check to see if we have tried all fractions with current x denominator
Y = 1 'reset y
X = X + 1 'add one to x making it next denominator
END IF
SLOPE = X / Y 'calculate slope of line
LOOP UNTIL SLOPE = DECIMAL 'keep doing this until your slope equals your decimal

So the routine will start with a point at 1,1 and calculate its slope, then compare it to your decimal number. It steps through points until it reaches 3/4, which equals .75 - Yay! :)

I apologize for the messiness of that but it was something i came up with in a couple minutes (and its basic to boot :( ). Of course you will have to round the value you get for SLOPE each time to the desired number of decimal places or you will endlessly loop for numbers such as 1/3, etc.
Young Doc: No wonder this circuit failed. It says "Made in Japan".Marty McFly: What do you mean, Doc? All the best stuff is made in Japan.Young Doc: Unbelievable.
JohnBolton
JohnBolton
Here is an algorithm for converting a value to the closest fraction (given a maximum value for the denominator). It is based on Farey Sequences. It is probably much faster than finding GCDs and the results are much more useful. For example, using the suggestions above, .333333 will be converted to 333333/1000000, which is probably not what you want. Using this algorithm, you will get 1/3.
    void ClosestFraction( float value, int max_denominator, int & numerator, int & denominator )    {        int low_n = 0;        int low_d = 1;        int high_n = 1;        int high_d = 1;        int mid_n;        int mid_d;        do        {            mid_n = low_n + high_n;            mid_d = low_d + high_d;            if ( mid_n < value * mid_d )            {                low_n = mid_n;                low_d = mid_d;                numerator = high_n;                denominator = high_d;            }            else            {                high_n = mid_n;                high_d = mid_d;                numerator = low_n;                denominator = low_d;            }        } while ( mid_d <= max_denominator );    } 
Edit: minor corrections

[Edited by - JohnBolton on October 26, 2005 6:34:22 PM]
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
Extrarius
Extrarius
I had been working on a binary search of my own devising for several hours =-(
I had it working, but I was priming it with 'guesses' using my previous code, and sometimes it was overflowing (though I only realized that was the problem when I saw your code).
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
Extrarius
Extrarius
I noticed an interesting problem in my implementation that I'm not sure how to explain: This is a binary search (right?), so in each iteration it should halve the search space. This means it should take X iterations to search 2^X possibilities.

However, if I enter 0.1001001 as the decimal to convert, after 31 iterations (bits in an int, figured it would take 1 iter per bit if it's halving the space each time) it only has 1/10 as a best candidate, and it takes many more iterations to find 100/999

[Edited by - Extrarius on October 27, 2005 1:37:00 AM]
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
Extrarius
Extrarius
While I'm still not sure why so many iterations are required, I believe I have improved the algorithm posted by JohnBolton somewhat:
while((numeric_limits<unsigned int>::max() - Low.Denominator > High.Denominator)	&& (numeric_limits<unsigned int>::max() - Low.Numerator > High.Numerator)){	Middle.Numerator = Low.Numerator + High.Numerator;	Middle.Denominator = Low.Denominator + High.Denominator;	if(double(Middle.Numerator) < FractionPart * double(Middle.Denominator))	{		Low = Middle;	}	else	{		High = Middle;	}	if(fabs((double(Middle.Numerator) / double(Middle.Denominator) - FractionPart)) < (PercentError * FractionPart))	{		break;	}	++Iterations;}
After the loop, the program selects either High or Low, whichever is closest to the actual fraction.

This way, the algorithm can run until it would overflow, but doing so can mean it will run a LOT of times (4299374 times to find 100/999) if you don't allow any error. Using a PercentError of 0.000001 reduces the number of iterations for 100/999 to only 107, but it also means that '.1001' comes out as 501/5005 ~= 0.1000999000999.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.