Decimal to Fraction
Author
I need to turn a decimal number into a fraction. Something like 0.57142857... to 4/7. Any ideas?
Here's a better idea. Compute the continued fraction expansion of your number.
x = 0.57142857
x = 1/1.75000000437500001093
x = 1/(1+1/1.33333332555555558149)
x = 1/(1+1/(1+1/3.00000007000000139992))
x = 1/(1+1/(1+1/(3+1/14285714.00001633224424480235)))
Stop now that you found a large number in the continued fraction expansion. Basically, assume that number should have been infinity, and compute the fraction you have so far.
x = 1/(1+1/(1+1/3)) = 4/7
x = 0.57142857
x = 1/1.75000000437500001093
x = 1/(1+1/1.33333332555555558149)
x = 1/(1+1/(1+1/3.00000007000000139992))
x = 1/(1+1/(1+1/(3+1/14285714.00001633224424480235)))
Stop now that you found a large number in the continued fraction expansion. Basically, assume that number should have been infinity, and compute the fraction you have so far.
x = 1/(1+1/(1+1/3)) = 4/7
No-brainer answer: any float can be written as (big integer)/2^m, where m is the number of mantissa bits (24? I forget).
If you want to get denominators like 3, 7 and so on to come out right, you're going to have to do some approximation because floats are only limited precision. Something like alvaro's solution is good.
If you want to get denominators like 3, 7 and so on to come out right, you're going to have to do some approximation because floats are only limited precision. Something like alvaro's solution is good.
I posted this in another thread a while back that had an excellent discussion of the problem, and I'm fairly certain that my solution is far from optimal, but I can't find the thread or any of the sites I used to construct my solution. Dec2Frac
Edit: I noticed that the GDNet hosting shows the 'last modified' time for files and I was able to use that to find the thread, which is How do I Convert a Decimal to a Fraction in c++?
Edit: I noticed that the GDNet hosting shows the 'last modified' time for files and I was able to use that to find the thread, which is How do I Convert a Decimal to a Fraction in c++?
An efficient way to compute the fraction that is closest to a value while limiting the denominator is to compute the terms of something called a "farey sequence". In your example the iterations of the computation for 0.57142857 would look like this:
Between -> New Bound ========== ========= 0/1, 1/1 -> 1/2 (lower) 1/2, 1/1 -> 2/3 (upper) 1/2, 2/3 -> 3/5 (upper) 1/2, 3/5 -> 4/7 (upper) 1/2, 4/7 -> 5/9 (lower) 5/9, 4/7 -> 9/16 (lower) 9/16, 4/7 -> 13/23 (lower) 13/23, 4/7 -> 17/30 (lower) 17/30, 4/7 -> 21/37 (lower) 21/37, 4/7 -> 25/44 (lower) 25/44, 4/7 -> 39/51 (lower) ... 53/93, 4/7 -> 57/100 (lower) 57/100, 4/7 -> 61/107 (lower) ... -> 57142857/100000000
Interesting solutions you guys have......but when I came up against this problem, I just switched to using rational numbers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
