Проверьте, является ли число рациональным в Python для заданной точности fp - PullRequest
Новая
       25

Проверьте, является ли число рациональным в Python для заданной точности fp

8 голосов
/ 24 ноября 2010

Я хотел бы знать хороший способ проверки, является ли число x рациональным (существуют два целых числа n, m, так что x = n / m) в python.

В Mathematica это выполняется функцией Rationalize[6.75]: 27/4

Я предполагаю, что на этот вопрос есть ответ для заданной точности. Существует ли общий алгоритм получения этих двух целых чисел?

Ответы [ 7 ]

13 голосов
/ 24 ноября 2010

В python> = 2.6 существует метод as_integer_ratio для чисел с плавающей запятой: 

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

Однако из-за способа определения чисел с плавающей запятой в языках программирования нет иррациональных чисел .

8 голосов
/ 24 ноября 2010

Природа чисел с плавающей точкой означает, что нет смысла проверять , является ли число с плавающей точкой рациональным, поскольку все числа с плавающей точкой на самом деле являются дробями вида n / 2 e .Однако вы, возможно, захотите узнать, существует ли простая дробь (с небольшим знаменателем, а не с большой степенью 2), которая близко приближается к данному числу с плавающей запятой.

Дональд Кнут обсуждает эту последнюю проблему в Искусство компьютерного программирования том 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)
5 голосов
/ 24 ноября 2010

Любое число с конечным десятичным разложением является рациональным числом.Вы всегда можете решить, например, 

5.195181354985216

, сказав, что оно соответствует 

5195181354985216 / 1000000000000000

Так что, поскольку числа с плавающей запятой и двойные числа имеют конечную точность, все они рациональны.

4 голосов
/ 24 ноября 2010

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)
4 голосов
/ 24 ноября 2010

Может быть это будет вам интересно: Наилучшее рациональное приближение

1 голос
/ 24 ноября 2010

Как вы заметили, любое число с плавающей запятой можно преобразовать в рациональное число, переместив десятичную точку и разделив на соответствующую степень десяти.

Затем вы можете удалить наибольший общий делитель из делимого и делителяи проверьте, соответствуют ли оба эти числа типу данных по вашему выбору.

0 голосов
/ 24 ноября 2010

Проблема с действительными числами в языках программирования состоит в том, что они обычно определяются как функции, возвращающие конечное представление с заданной точностью (например, функция, которая принимает n в качестве аргумента и возвращает число с плавающей запятой с точностью до 2 ^ -n) .

Вы можете определенно превратить рациональное / целое число в действительное, но даже сравнение вещественных чисел на равенство неразрешимо (по сути, это проблема остановки).

Вы не можете сказать, рационально ли действительное число x: даже в математике это обычно сложно, так как вам нужно найти p и q, такие что x = p / q, и это часто неконструктивно.

Однако, учитывая окно точности, вы можете найти «наилучшее» рациональное приближение для этой точности, используя, например, непрерывное расширение дроби. Я полагаю, что это в основном то, что делает Mathematica. Но в вашем примере 6.75 уже рационально. Вместо этого попробуйте Пи.

...