Compruebe si un número es racional en Python, para una precisión de fp dada

Me gustaría saber una buena manera de verificar si un número x es un racional (existen dos enteros n, m para que x = n / m) en python.

En Mathematica, esto se realiza mediante la función Rationalize[6.75] : 27/4

Asumo que esta pregunta tiene una respuesta para una precisión dada. ¿Existe un algoritmo común para obtener estos dos enteros?

En python> = 2.6 hay un método as_integer_ratio en floats:

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

Sin embargo, debido a la forma en que se definen los flotadores en los lenguajes de progtwigción, no hay números irracionales .

La naturaleza de los números de punto flotante significa que no tiene sentido verificar si un número de punto flotante es racional, ya que todos los números de punto flotante son realmente fracciones de la forma n / 2 e . Sin embargo, es posible que desee saber si hay una fracción simple (una con un denominador pequeño en lugar de una gran potencia de 2) que se aproxima mucho a un número de punto flotante dado.

Donald Knuth analiza este último problema en el volumen II de The Art of Computer Programming . Consulta la respuesta al ejercicio 4.53-39. La idea es buscar la fracción con el denominador más bajo dentro de un rango, expandiendo los puntos finales del rango como fracciones continuas siempre que sus coeficientes sean iguales, y luego, cuando difieren, toman el valor más simple entre ellos. Aquí hay una implementación bastante sencilla en 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) 

Y aquí hay algunos resultados:

 >>> 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) 

Cualquier número con una expansión decimal finita es un número racional. Siempre se podría resolver por ejemplo.

 5.195181354985216 

diciendo que corresponde a

 5195181354985216 / 1000000000000000 

Entonces, como los flotadores y los dobles tienen una precisión finita, todos son racionales.

Puede ser que esto sea interesante para usted: la mejor aproximación racional

Python usa representación de punto flotante en lugar de números racionales. Eche un vistazo al módulo de fractions biblioteca estándar para obtener algunos detalles sobre los números racionales.

Observe, por ejemplo, esto, para ver por qué sale mal:

 >>> 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, ¿quieres ver un caso donde funcione?)

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

Como notó, cualquier número de punto flotante se puede convertir en un número racional moviendo el punto decimal y dividiendo por el poder apropiado de diez.

Luego, puede eliminar el mayor divisor común del dividendo y del divisor y verificar si estos dos números se ajustan al tipo de datos de su elección.

El problema con los números reales en los lenguajes de progtwigción es que generalmente se definen como funciones que devuelven una representación finita con una precisión (por ejemplo, una función que toma n como argumento y devuelve un número de punto flotante con una precisión de 2 ^ -n).

Definitivamente, puedes convertir un racional / entero en un real, pero incluso comparar los reales por la igualdad es indecidible (es esencialmente el problema que se detiene).

No se puede saber si un número real x es racional: incluso en matemáticas, por lo general es difícil, ya que tiene que encontrar p y q tal que x = p / q, y esto a menudo no es constructivo.

Sin embargo, dada una ventana de precisión, puede encontrar la “mejor” aproximación racional para esta precisión utilizando, por ejemplo, la expansión continua de fracciones. Creo que eso es esencialmente lo que hace mathica. Pero en tu ejemplo, 6.75 ya es racional. Pruebe con Pi en su lugar.