need library to convert a decimal number to fraction (rational)?

[ronenp88]

hello everyone, I don't know to do this myself, so I rather use a library, I need to convert decimal numbers to fractions (closest possible fraction in lowest terms), can anyone point me a direction?
thank you!

[lastchance]

Not quite as simple as you might think.

Most "decimal" numbers would be stored as floating-point doubles, known only to a finite accuracy because of binary representation. So you would have to enter the number as a string.

- Acting on the string representation, separate off the parts before and after the decimal point.
- Take note of, then strip off, the sign.
- Convert the whole number and remainder separately to integers and, from the fractional part (giving the numerator) calculate the denominator as the appropriate power of 10.
- Dealing with the fractional part divide numerator and denominator by their highest common factor.
- Adjust the numerator for any whole number component.
- Put the sign back in the numerator if the original number was negative

[ronenp88]

thanks for your reply, but I will do that only if I must, no one solved this in some library?

[Duthomhas]

Forgive us, but this is a pretty standard homework question requiring basic math. Key is to use the GCD function, as lastchance points out.

I'm pretty sure a lot of bignum libraries can do it, such as Boost.Multiprecision.

[ronenp88]

thanks I will try boost

[ronenp88]

"The library does not offer a conversion function from floating point to rational. A number of requests were received for such a conversion, but extensive discussions on the boost list reached the conclusion that there was no "best solution" to the problem. As there is no reason why a user of the library cannot write their own conversion function which suits their particular requirements, the decision was taken not to pick any one algorithm as "standard". "
seems like boost don't manage to do it.

[lastchance]

This is a bit "fragile" (don't try too many "ill-formed" strings, cases where numerator or denominator go out of range of an integer, anything involving scientific notation). It would be made much more complicated to have to cover each of those. To do: put in proper error-checking.

#include <iostream>
#include <string>
#include <utility>
#include <cmath>
using namespace std;


const char DECIMAL_POINT = '.';        // language-dependent


//======================================================================


int hcf( int a, int b )
{
   int q = 1;

   while ( b > 0 )
   {
      q = b;
      b = a % q;
      a = q;
   }
   return q;
}


//======================================================================


pair<int,int> fraction( string s )
{
   string whole, fract;

   // Split into substring representing whole number and fractional part
   int pos = s.find( DECIMAL_POINT );
   if ( pos == string::npos )
   {
      whole = s;
   }
   else
   {
      whole = s.substr( 0, pos );
      if ( pos < s.size() - 1 ) fract = s.substr( pos + 1 );
   }
   if ( whole == "" ) whole = "0";
   if ( fract == "" ) fract = "0";

   // Sort out the fractional part as p / q
   int p = stoi( fract );
   int q = 1, pp = p;
   while ( pp ) { q *= 10;   pp /= 10; }

   // Strip the HCF out
   int h = hcf( p, q );
   p /= h;
   q /= h;

   // Adjust for whole number and sign
   bool negative = ( whole.find( '-' ) != string::npos );
   int w = abs( stoi( whole ) );
   p += q * w;
   if ( negative ) p = -p;

   return { p, q };
}


//======================================================================


int main()
{
   string tests[] = { "0.234", "1.12", "10.5", "10.0", "10.", "-10.30", "-123", "-0.65" };
   for ( string s : tests )
   {
      pair<int,int> p = fraction( s );
      cout << s << " ---> " << p.first << " / " << p.second << '\n';
   }
}

0.234 ---> 117 / 500
1.12 ---> 28 / 25
10.5 ---> 21 / 2
10.0 ---> 10 / 1
10. ---> 10 / 1
-10.30 ---> -103 / 10
-123 ---> -123 / 1
-0.65 ---> -13 / 20

[ronenp88]

thank you I will try now to do it by myself and post questions or troubles during this process, here, for more help if needed, thanks

[ronenp88]

how I figure out the repeating decimal pattern?

[lastchance]

ronenp88 wrote:

how I figure out the repeating decimal pattern?

Maybe you should show your code so that we can see exactly what you are trying to do.

[Repeater]

How would you even type in a repeating decimal pattern?

[ronenp88]

I didn't code yet, I try to understand first what I'm doing, so far I don't know really what to do, I just know that if its repeating then I take the repeating numbers and divide by 999... n 9's as the repeating part, and then reduce to lowset terms

[lastchance]

e.g.
12.34567567567....
which I'd write in a linear fashion as
12.34(567)
I've bracketed the repeating bit.

You don't have to, but it's easier (I think) to separate the non-repeating and repeating bits.
12.34 + 0.00(567)

The non-repeating bit, 12.34, is easy. You can deal with that and add it as a fraction later.

So let's concentrate on
x = 0.00(567)
Look at the length of the repeating bit. Here, it's 3, so multiply by 10³, or 1000.
1000x = 5.67(567)

Then subtract:
999x = 5.67 = 567/100
so
x = 567/99900

Finally you go back and sort out the whole thing:
1234/100 + 567/99900 = ... whatever

And now I understand why Boost didn't want to do it!

[Duthomhas]

For a homework or even simple usage all you need to do is put reasonable limits on the patterns.

Ah, yes.
Boost didn't want to do it because there are extremely obscure technical issues that arise in important corner cases, and the way it is done has an impact on its usability in any given application. Hence, Boost would rather you write the code to satisfy your requirements.

[jonnin]

/shrug for practical purposes, cant you just craft something/pow(10, something)?
eg even a repeating thing like
1.234234234234 is 1234234234234 /1000000000000 (if I counted the zeros right, not checking it but you get the point). then just reduce the above with GCD calls or something if you need it reduced. Is that good enough for what you wanted?

I mean its provable in math (see, irrational numbers) that not everything can be written exactly as a fraction. So knowing that going into this, you have to make some decisions on how much trouble you want to go into.... the above will get you a long, long way for homework type problems.

you don't have to do anything for repeating decimals. Just run the precision as far as you want, or as far as double supports, and use this approximate value. Repeating numbers are not irrational, but finding the exact fraction is .... extremely difficult. Finding an approximate fraction should be good enough.

[Duthomhas]

Floating point numbers are an approximation themselves, so the question comes down to, how much effort do you want to put into precision?

Even if you are computing parallax to stars you can get away with six or seven decimal places.

The ratios that will give you the most grief are those involving primes or values very close to primes. But again, this is just part of the precision issue you have to accept as a reality of rational numbers systems.

[ronenp88]

rational simplify_fraction(rational r) {
	long long int i = std::abs(r.num) < std::abs(r.denom) ? std::abs(r.num) : std::abs(r.denom);
	for (; i >= 2; i--) {
		if (r.num%i == 0 && r.denom%i == 0) {
			r.num = r.num / i;
			r.denom = r.denom / i;
		}
	}
	return r;
}

Does this function of simplifying fractions appropriate enough?

[Duthomhas]

That looks fine. If it works, you're golden.