Jump to content
  • Advertisement
Sign in to follow this  
SuperNerd

Decimal to Fraction

This topic is 4275 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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++?

Share this post


Link to post
Share on other sites
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
Do you see the pattern? The beauty is that you can stop anytime and return the closest of the two bounds. So, in this case if you limit the denominator to 100, your answer would be 4/7.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!