Check if a number is rational in Python, for a given fp accuracy

I would like to kn开发者_开发百科ow a good way of checking if a number x is a rational (two integers n,m exist so that x=n/m) in python.

In Mathematica, this is done by the function Rationalize[6.75] : 27/4

I assume this question has an answer for a given accuracy. Is there a common algorithm of obtaining these two integers?

In python >= 2.6 there is a as_integer_ratio method on floats:

>>> a = 6.75
>>> a.as_integer_ratio()
(27, 4)
>>> import math
>>> math.pi.as_integer_ratio()
(884279719003555, 281474976710656)

However, due to the way floats are defined in programming languages there are no irrational numbers.

The nature of floating-point numbers means that it makes no sense to check if a floating-point number is rational, since all floating-point numbers are really fractions of the form n / 2^e. However, you might well want to know whether there is a simple fraction (one with a small denominator rather than a big power of 2) that closely approximates a given floating-point number.

Donald Knuth discusses this latter problem in The Art of Computer Programming volume II. See the answer to exercise 4.53-39. The idea is to search for the fraction with the lowest denominator within a range, by expanding the endpoints of the range as continued fractions so long as their coefficients are equal, and then when they differ, take the simplest value between them. Here's a fairly straightforward implementation in Python:

from fractions import Fraction
from math import modf

def simplest_fraction_in_interval(x, y):
    """Return the fraction with the lowest denominator in [x,y]."""
    if x == y:
        # The algorithm will not terminate if x and y are equal.
        raise ValueError("Equal arguments.")
    elif x < 0 and y < 0:
        # Handle negative arguments by solving positive case and negating.
        return -simplest_fraction_in_interval(-y, -x)
    elif x <= 0 or y <= 0:
        # One argument is 0, or arguments are on opposite sides of 0, so
        # the simplest fraction in interval is 0 exactly.
        return Fraction(0)
    else:
        # Remainder and Coefficient of continued fractions for x and y.
        xr, xc = modf(1/x);
        yr, yc = modf(1/y);
        if xc < yc:
            return Fraction(1, int(xc) + 1)
        elif yc < xc:
            return Fraction(1, int(yc) + 1)
        else:
            return 1 / (int(xc) + simplest_fraction_in_interval(xr, yr))

def approximate_fraction(x, e):
    """Return the fraction with the lowest denominator that differs
    from x by no more than e."""
    return simplest_fraction_in_interval(x - e, x + e)

And here are some results:

>>> approximate_fraction(6.75, 0.01)
Fraction(27, 4)
>>> approximate_fraction(math.pi, 0.00001)
Fraction(355, 113)
>>> approximate_fraction((1 + math.sqrt(5)) / 2, 0.00001)
Fraction(377, 233)

Any number with a finite decimal expansion is a rational number. You could always solve for instance

5.195181354985216

by saying that it corresponds to

5195181354985216 / 1000000000000000

So since floats and doubles have finite precision they're all rationals.

Python uses floating-point representation rather than rational numbers. Take a look at the standard library fractions module for some details about rational numbers.

Observe, for example, this, to see why it goes wrong:

>>> from fractions import Fraction
>>> 1.1  # Uh oh.
1.1000000000000001
>>> Fraction(1.1)  # Will only work in >= Python 2.7, anyway.
Fraction(2476979795053773, 2251799813685248)
>>> Fraction(*1.1.as_integer_ratio())  # Python 2.6 compatible
Fraction(2476979795053773, 2251799813685248)

(Oh, you want to see a case where it works?)

>>> Fraction('1.1')
Fraction(11, 10)

May be this will be interesting to you: Best rational approximation

As you noted any floating point number can be converted to a rational number by moving the decimal point and dividing by the appropriate power of ten.

You can then remove the greatest common divisor from the dividend and divisor and check if both of these numbers fit in the data type of your choice.

The problem with real numbers in programming languages is that they are usually defined as functions returning a finite representation given an accuracy (eg. a function which takes n as an argument and returns a floating point number within 2^-n accuracy).

You can definitely turn a rational/integer into a real, but even comparing reals for equality is undecidable (it is essentially the halting problem).

You cannot tell whether a real number x is rational: even in mathematics, it is usually difficult, since you have to find p and q such that x = p/q, and this is often non constructive.

However, given an accuracy window, you can find the "best" rational approximation for this accuracy using for instance continuous fraction expansion. I believe that is essentially what mathematica does. But in your exemple, 6.75 is already rational. Try with Pi instead.