Thread: Program to convert from decimal to fraction

1. Program to convert from decimal to fraction

Please does anybody know an algorithm which can be used to convert a decimal to a fraction especially irrational fractions thanks. That is a programm that can convert to 0.333333333333333333333 to 1/3 like any scientific calculator does.

2. You need to find the length of the repeating pattern and set n = length of repeating pattern. Then multiply the number by 10^n, then subtract that number from 10^n times the number. The result will be (10^n - 1) times the number, and an integer. Then that integer divided by (10^n - 1) is the fraction. After this, use Euclid algorithm to find greatest common divisor to reduce the fraction.

For example 1/7 = 0.142857142857142857142857142857..., that's a 6 digit pattern. You need to multiply this number by 10^6 to get 142857. .... Then subtract the original number resulting in (10^6 - 1) x number = 142857. The fraction is 142857 / 999999 and in this case the greatest common divisor is 142857, so the result is 1/7.

3. Check out continued fractions and Euclidean algorithm at Wikipedia.

4. Originally Posted by acho.arnold
especially irrational fractions
An irrational ("not a ratio") number is one that cannot be written as a fraction, so there are no irrational fractions.
To figure out an algorithm, figure out how you would do it yourself.

5. You'll also need to check for fractions that are exact decimal values, such as .1520000000. For these, you'll need to multiply by 10, then subtract the integer part to see if the fractional part is zero (or nearly zero, you'll need some tolerance here), and if not repeat process. In this case after 3 multiplies by 10, you get the integer 152, so the fraction is 152/1000, with a greatest common divisor of 8 resulting in 19/125.

6. Originally Posted by rcgldr
You'll also need to check for fractions that are exact decimal values, such as .1520000000. For these, you'll need to multiply by 10, then subtract the integer part to see if the fractional part is zero (or nearly zero, you'll need some tolerance here), and if not repeat process. In this case after 3 multiplies by 10, you get the integer 152, so the fraction is 152/1000, with a greatest common divisor of 8 resulting in 19/125.
That technique still needs to be applied in a case like 2/15:
0.1333333333333333333
So you could consider the first 0 in .1520000000 as being the repeating part.

You may end up needing some big number math here if the fractional part of an irrational is given (no repeating part).

Also, in general it's not possible to recover the fraction that was used to generate the float since the float's limited precision essentially represents the actual rationals in lumps, like the pixels on a screen represent space in lumps.

I was thinking of another scheme, dividing the number (assumed to be < 1) into 1.
If the result has no fractional part, the fraction is 1 over the result.
Otherwise,
* continue taking multiples of result until it has no fractional part;
* the final result is the denominator and the number of the multiple is the numerator.

7. I just wrote a roughly 120-line test program based on continued fractions, and Euclidean algorithm for removing common factors from the numerator and denominator.

The only "extra" parameters it needs is the maximum number of factors, and the largest integer factor in the continued fraction. These determine the precision of the result.

The idea is as follows.

Split a positive value to integral and fractional parts (using e.g. modf()). This yields you
value = integral + fractional
Since the fractional part is always between zero and one (exclusive), you can approximate it with a reciprocal of an integer:
value ≃ integral + 1/reciprocal
Note that if the fractional part is zero, you have an exact representation. If the reciprocal is just an approximation, you can make it more precise by repeating the process:
value ≃ a0 + 1/(a1 + 1/(a2 + ... 1/aN))
Since the right-side values are all integers, you can combine them to the desired fractional representation:
a0 + 1/a1 = (a0*a1+1)/a1
a0 + 1/(a1 + 1/a2) = a0 + a2/(a1*a2+1) = (a0*(a1*a2+1)+a2) / (a1*a2+1)
:
and so on.

The numerator and denominator often have common divisors, so you need to use the Euclidean algorithm to find the largest common divisor between the two, and divide both by it, to get the normal fractional form.

Here is a worked-out example:
Code:
```1.24 = 1 + 0.24
1.24 = 1 + 1/(4 + 0.1666..)
1.24 = 1 + 1/(4 + 1/6)

Exact using three factors, 1, 4, 6, in a continued fraction.

1.24 = 1 + 1/(4 + 1/6)
1.24 = 1 + 1/(25/6)
1.24 = 1 + 6/25
1.24 = (25 + 6)/25
1.24 = 31 / 25```
In practice, you'll have one loop that first deconstructs the value into the continued fraction form, using two or more integer factors as above. (If you only have one, then the solution is trivial and exact.)

A second loop starts with the last two factors, assigns them as current numerator and denominator, and walks back the array of factors. (Just like you would on paper: start at the lower right column, step by step.) At each step, you need to use the Euclidean algorithm to remove common divisors from the numerator and denominator. I used the iterative version of the Stein algorithm.

Finally, you'll want to add the original integral part of the value to the numerator and denominator, and adjust sign if necessary.

Here are some test numbers and their results my program gets with maximum 8 coefficients (including the integral part of the original value), limiting the coefficients to less than 1000:
Code:
```2.4 = 12 / 5
2.91 = 291 / 100
3.33 = 333 / 100
8.458 = 4229 / 500
3.333 = 3333 / 1000
1.5221 = 7335 / 4819
3.3333 = 10 / 3
5.85537 = 1417 / 242
1.934754 = 45577 / 23557
8.1062270 = 279754 / 34511
1.73530690 = 3986 / 2297
4.849832125 = 5781 / 1192
1.5186262650 = 2609 / 1718```

8. Originally Posted by oogabooga
I was thinking of another scheme, dividing the number (assumed to be < 1) into 1.
Also called an continued fraction, which I referred to post #3, and everyone completely ignored. Harrumph.

9. Originally Posted by Nominal Animal
Also called an continued fraction, which I referred to post #3, and everyone completely ignored. Harrumph.
I ended up reading the wikipedia link you gave, but not until after I posted. I realized that it was the same idea!

10. Originally Posted by Nominal Animal
I just wrote a roughly 120-line test program based on continued fractions, and Euclidean algorithm for removing common factors from the numerator and denominator.
That's about the size I thought that continued fraction method would be. I was thinking the repeated decimal string method might take less code, but once all the variations are handled, it probably ends up taking even more code.

11. Originally Posted by rcgldr
That's about the size I thought that continued fraction method would be. I was thinking the repeated decimal string method might take less code, but once all the variations are handled, it probably ends up taking even more code.
My impl is just a few lines. I haven't tested it extensively, though.
EDIT:
Also, it doesn't need the gcd. It seems to be related to continued fractions, but is not really the same thing. I think it works, but it may not be too efficient.

12. Originally Posted by oogabooga
My impl is just a few lines.
My verbose continued fraction function is 41 lines of code (not including comments or empty lines); the function dividing both numerator and denominator with their greatest common divisor is an additional 28 lines (not including comments or empty lines). The rest is command-line parameter parsing etc.

I didn't bother to work out how to easily manage the overall precision, as my mind is not at its sharpest right now, but it shouldn't be too difficult. Double-precision random numbers seem to require up to 24 or so integer factors in the continuous fraction to yield a fraction within LSB of the original value, but the temporary results (multiplications and additions before using GCD to remove the greatest common divisor) tend to overflow even 64-bit integers sometimes; I used 16 iterations for the tests, for about ten-twelve digits of precision.

My current function seens to take about 6000 clock cycles on x86-64 to determine 1.24 = 31/25, and between 5000 and 14000 cycles for random double-precision floating-point numbers. It is rare for there to be common divisors in the numerator and denominator -- I didn't encounter any test value where at any point during the computation the numerator and denominator shared a common divisor -- but the math indicates it might be needed; it's just rare.

So, I'd say even the simple approach, generating the fraction and the value it represents for each increasing number of continuous fraction factors, and comparing the error between the result and the original value, should be quite fast enough for real world use cases. I'd estimate something of the order of 100,000 cycles for a simple, straightforward implementation; much less if you care to optimize the logic.

This is simple enough that I do believe calculators etc. use an exact or at least very similar algorithm.

13. I have a custom C++ fraction data type that does this using a fast convergence algorithm. Its loop contains just 1x fabs, 3x floor, 2x division, 2x multiplication, 2x addition, 2x subtraction, and 4x comparisons. It needs no special case code for mixed-numbers, a.k.a improper fractions, does not make use or recurring decimals, does not convert to string, and it has no multiplications or divisions by powers of ten. The gcd is not required for simplifying the fraction afterwards either.

It has unit tests that prove the correct answer for every possible fraction where the numerator and denominator sum to under 2000 (my tests can go at least 10x higher but that takes a long time), where both are positive of course. e.g. this is no problem:
Code:
```double val = 577.0 / 1361.0;
fract fr = val;
assert(fr.numer == 577 && fr.denom == 1361);```
So, um yes I know the ideal algorithm. If you search the next hard enough you'll find it.

14. Originally Posted by iMalc
It needs no special case code for mixed-numbers, a.k.a improper fractions
Does it yield a good approximation for those, or does it just punt? What does it yield for example for 0.9999127?

Originally Posted by iMalc
So, um yes I know the ideal algorithm. If you search the next hard enough you'll find it.
Bold claim. Care to link to the basis (articles, references?) of that claim?

15. Originally Posted by acho.arnold
Please does anybody know an algorithm which can be used to convert a decimal to a fraction especially irrational fractions thanks.
That's impossible. An irrational value, by definition, means it cannot be expressed as a fraction (i.e. in the form of one integer divided by another). If it could be expressed as a fraction, it would be a rational value, not an irrational value.

Originally Posted by acho.arnold
That is a programm that can convert to 0.333333333333333333333 to 1/3 like any scientific calculator does.
Scientific calculators do not do that, not matter how it might seem.

If you divide 1 by 3, you might get a value which looks like 0.3333333333333 but, depending on the program, it might remember the two values divided. So any imprecision is cancelled out. In other words, programs which do that work with fractions internally (alternatively, they may simply round up 0.9999999999 to 1, if the number of decimal places exceeds some specified value).

In any event, the algorithm is the sum of each digit multiplied by 10^-n where n is the number of places the digit is after the decimal point.

Popular pages Recent additions