0

Possible Duplicate:
How to convert floats to human-readable fractions?

I have a floating point value say 0.595781 which I would like to get as close to as possible using a quotient that uses only integer numerator and denominator values which are both limited in range from 0 to 1023 (10-bits).

The intuitive way to do this (at least to start off) would be use 595/1000 which provides 0.555 a fairly close match (the error is 0.040781).

But there is a better match of 597/1002 which is 0.595808 (an error of 0.0000273). There may be better matches also. I came to the second quotient by playing about with the numerator and denominator values close to their original values in an irrerative way.

I then wondered if there was a way given all the criteria to get the numerator and denominator integer values directly.

In case your wondering the two integer values are required to setup the baud rate generator for an Infineon XE167G device.

Any ideas would be appreciated. Regards

Community
  • 1
  • 1
user1704021
  • 51
  • 5
  • 1
    why would 595/1000 be intuitive when simple rounding leads you to 596/1000 being closer? – TJD Sep 27 '12 at 17:07
  • 1
    What you want is the [best rational approximation](https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations) for the denominator d=1024. This is answered in the duplicate linked by Borgleader. – Douglas B. Staple Sep 27 '12 at 20:49
  • For best precision you use the highest demoninator available (for values from 0 to 1023 this is 512) which is a power of two. Then the first numerator is round(512*value). This guarantees a precision which is always less than 1/512 because the floating-point value is binary. To correct the denominator for better precision you calculate a correction term = (numerator/value)-denominator which is added to your denominator. – Thorsten S. Sep 28 '12 at 11:09
  • To correct the denominator for better precision you calculate a correction term = (numerator/value)-denominator which is added to your denominator. Example: 0.595781*512 = 305. correction = (305/0.59..)-512 = -0.06 (no correction). So you get 305/512 which is 0.595703 which is only marginally worse than 0.595808 – Thorsten S. Sep 28 '12 at 11:18
  • 305/512 gives an approximation but 339/569 gives a closer one. The problem I am trying to solve is how to get the best approximation given the denominator and numerator range constraints. The reference to a previous post (that closed this thread) is not appropriate as it stands because it does not limit the numerator range. – user1704021 Sep 28 '12 at 12:01
  • Yes, but using http://en.wikipedia.org/wiki/Continued_fraction which solves the general problem is the option to take. It gives the result in always more precise fractions, so you need to use the last one you can still us. So if you don't want to use the method it is probably better to have sth which gives *good* results. If my solution does not satisfy you, either you try to use continued fractions or test *all* valid combinations with brute force. There is nothing else left. – Thorsten S. Oct 01 '12 at 14:28

1 Answers1

0

If you are using 16-bit integers, you could just have numerator = 59578 and denominator just hold a power factor of 10, for instance 5. So the answer would be 59578/(10^5).

With this approach you would at least keep 4 places of precision. Just a thought...

Coding Mash
  • 3,338
  • 5
  • 24
  • 45
Nanomurf
  • 709
  • 3
  • 12
  • 32
  • Thanks. The problem is that both the numerator and denominator can only have maximum values of 1023 (10-bits) which makes the problem more difficult than it appears. Its a case of finding an algorithm for direct calculation of the numerator and denominator or an interrative method that does some trial and error perhaps. Regards – user1704021 Sep 27 '12 at 17:53