Precision issues when converting a decimal number to its rational equivalent

Question

I have problem of converting a double (say N) to p/q form (rational form), for this I have the following strategy :

1. Multiply double N by a large number say $k = 10^{10}$
2. then p = y*k and q = k
3. Take gcd(p,q) and find p = p/gcd(p,q) and q = p/gcd(p,q)

when N = 8.2 , Answer is correct if we solve using pen and paper, but as 8.2 is represented as 8.19999999 in N (double), it causes problem in its rational form conversion.

I tried it doing other way as : (I used a large no. 10^k instead of 100)

if(abs(y*100 - round(y*100)) < 0.000001) y = round(y*100)/100

But this approach also doesn't give right representation all the time.

Is there any way I could carry out the equivalent conversion from double to p/q ?

Answer 1

Floating point arithmetic is very difficult. As has been mentioned in the comments, part of the difficulty is that you need to represent your numbers in binary.

For example, the number 0.125 can be represented exactly in binary:

0.125 = 2^-3 = 0b0.001

But the number 0.12 cannot.

To 11 significant figures:

0.12 = 0b0.00011110101

If this is converted back to a decimal then the error becomes obvious:

0b0.00011110101 = 0.11962890625

So if you write:

double a = 0.2;

What the machine actually does is find the closest binary representation of 0.2 that it can hold within a double data type. This is an approximation since as we saw above, 0.2 cannot be exactly represented in binary.

One possible approach is to define an 'epsilon' which determines how close your number can be to the nearest representable binary floating point.

Here is a good article on floating points:

https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

Answer 2

have problem of converting a double (say N) to p/q form
... when N = 8.2

A typical double cannot encode 8.2 exactly. Instead the closest representable double is about

8.19999999999999928945726423989981412887573...
8.20000000000000106581410364015027880668640...  // next closest

When code does

double N = 8.2;

It will be the 8.19999999999999928945726423989981412887573... that is converted into rational form.

---

Converting a double to p/q form:

Multiply double N by a large number say $k = 10^{10}$

This may overflow the double. First step should be to determine if the double is large, it which case, it is a whole number.

Do not multiple by some power of 10 as double certainly uses a binary encoding. Multiplication by 10, 100, etc. may introduce round-off error.

---

C implementations of double overwhelmingly use a binary encoding, so that FLT_RADIX == 2.

Then every finite double x has a significand that is a fraction of some integer over some power of 2: a binary fraction of DBL_MANT_DIG digits @Richard Critten. This is often 53 binary digits.

Determine the exponent of the double. If large enough or x == 0.0, the double is a whole number.

Otherwise, scale a numerator and denominator by DBL_MANT_DIG. While the numerator is even, halve both the numerator and denominator. As the denominator is a power-of-2, no other prime values are needed for simplification consideration.

#include <float.h>
#include <math.h>
#include <stdio.h>

void form_ratio(double x) {
  double numerator = x;
  double denominator = 1.0;
  if (isfinite(numerator) && x != 0.0) {
    int expo;
    frexp(numerator, &expo);
    if (expo < DBL_MANT_DIG) {
      expo = DBL_MANT_DIG - expo;
      numerator = ldexp(numerator, expo);
      denominator = ldexp(1.0, expo);
      while (fmod(numerator, 2.0) == 0.0 && denominator > 1.0) {
        numerator /= 2.0;
        denominator /= 2.0;
      }
    }
  }
  int pre = DBL_DECIMAL_DIG;
  printf("%.*g --> %.*g/%.*g\n", pre, x, pre, numerator, pre, denominator);
}

int main(void) {
  form_ratio(123456789012.0);
  form_ratio(42.0);
  form_ratio(1.0 / 7);
  form_ratio(867.5309);
}

Output

123456789012 --> 123456789012/1
42 --> 42/1
0.14285714285714285 --> 2573485501354569/18014398509481984
867.53089999999997 --> 3815441248019913/4398046511104