Я хотел бы знать, как хорошо проверить, является ли число x рациональным (существуют два целых числа n, m, так что x = n / m) в python.
В Mathematica это делается с помощью функции Rationalize[6.75]: 27/4
Я предполагаю, что у этого вопроса есть ответ с заданной точностью. Есть ли общий алгоритм получения этих двух целых чисел?
В python> = 2.6 есть метод as_integer_ratio для чисел с плавающей запятой:
>>> a = 6.75
>>> a.as_integer_ratio()
(27, 4)
>>> import math
>>> math.pi.as_integer_ratio()
(884279719003555, 281474976710656)
Однако из-за того, как числа с плавающей запятой определены в языках программирования, нет иррациональных чисел.
Природа чисел с плавающей запятой означает, что нет смысла проверять, является ли число с плавающей запятой рациональным, поскольку все числа с плавающей запятой на самом деле являются дробями вида n / 2 e. Однако вы можете захотеть узнать, существует ли простая дробь (с малым знаменателем, а не с большой степенью двойки), которая близко аппроксимирует данное число с плавающей запятой.
Дональд Кнут обсуждает эту последнюю проблему в томе II Искусство компьютерного программирования. См. Ответ к упражнению 4.53–39. Идея состоит в том, чтобы искать дробь с наименьшим знаменателем в пределах диапазона, расширяя конечные точки диапазона как непрерывные дроби, пока их коэффициенты равны, а затем, когда они различаются, брать простейшее значение между ними. Вот довольно простая реализация на 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)
И вот некоторые результаты:
>>> 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)
x и y должны быть плавающими, а функция должна возвращать Fraction. Думаю, в этом случае лучше выдать ошибку.
- person Gareth Rees; 24.11.2010
Fraction(*x.as_integer_ratio()).
- person Gareth Rees; 24.11.2010
Любое число с конечным десятичным расширением является рациональным числом. Вы всегда можете решить, например,
5.195181354985216
говоря, что это соответствует
5195181354985216 / 1000000000000000
Итак, поскольку числа с плавающей запятой и двойные числа имеют конечную точность, все они рациональны.
Возможно, вам это будет интересно: Наилучшее рациональное приближение
Python использует представление с плавающей запятой, а не рациональные числа. Взгляните на стандартный библиотечный fractions модуль для получения некоторых сведений о рациональных числах.
Обратите внимание, например, на это, чтобы понять, почему что-то идет не так:
>>> 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)
(О, вы хотите увидеть случай, когда это работает?)
>>> Fraction('1.1')
Fraction(11, 10)
Как вы заметили, любое число с плавающей запятой можно преобразовать в рациональное число, переместив десятичную запятую и разделив ее на соответствующую степень десяти.
Затем вы можете удалить наибольший общий делитель из делимого и делителя и проверить, подходят ли оба этих числа к выбранному вами типу данных.
fractions.gcd().
- person martineau; 24.11.2010
Проблема с действительными числами в языках программирования заключается в том, что они обычно определяются как функции, возвращающие конечное представление с заданной точностью (например, функция, которая принимает n в качестве аргумента и возвращает число с плавающей запятой с точностью 2 ^ -n).
Вы определенно можете превратить рациональное / целое число в действительное, но даже сравнение действительных чисел на равенство неразрешимо (по сути, это проблема остановки).
Вы не можете сказать, рационально ли действительное число x: даже в математике это обычно сложно, так как вам нужно найти такие p и q, что x = p / q, а это часто неконструктивно.
Однако, учитывая окно точности, вы можете найти «лучшее» рациональное приближение для этой точности, используя, например, непрерывное расширение дроби. Я считаю, что математика именно этим и занимается. Но в вашем примере 6,75 уже рационально. Попробуйте вместо этого использовать Pi.
