Thread: 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.

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.

Check out continued fractions and Euclidean algorithm at Wikipedia.

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.

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.

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.

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

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.

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!

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.

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?