对于给定的 fp 精度，检查 Python 中的数字是否有理数

Question

我想知道在 python 中检查数字 x 是否是有理数（存在两个整数 n,m 使得 x=n/m）的好方法。

在 Mathematica 中，这是通过函数 Rationalize[6.75] 完成的：27/4

我假设这个问题有给定精度的答案。 是否有获取这两个整数的通用算法？

Answer 1

在 python >= 2.6 中，浮点上有一个 as_integer_ratio 方法：

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

但是，由于编程语言中定义浮点数的方式，不存在无理数。

Answer 2

浮点数的本质意味着检查浮点数是否有理数是没有意义的，因为所有浮点数实际上都是 n 形式的分数> / 2^e。但是，您可能很想知道是否存在一个非常接近给定浮点数的简单分数（分母较小，而不是 2 的大幂）。

Donald Knuth 在《计算机编程艺术》第二卷中讨论了后一个问题。请参阅练习 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)

Answer 3

任何具有有限小数展开式的数都是有理数。例如，您总是可以

5.195181354985216

通过说它对应于

5195181354985216 / 1000000000000000

So 来解决，因为浮点数和双精度数具有有限精度，它们都是有理数。

Answer 4

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)

Answer 5

您可能会对此感兴趣：最佳有理近似

Answer 6

正如您所指出的，任何浮点数都可以通过移动小数点并除以适当的十次方来转换为有理数。

然后，您可以从被除数和除数中删除最大公约数，并检查这两个数字是否符合您选择的数据类型。

Answer 7

编程语言中实数的问题在于，它们通常被定义为返回给定精度的有限表示的函数（例如，以 n 作为参数并返回 2^-n 精度内的浮点数的函数）。

您绝对可以将有理数/整数转换为实数，但即使比较实数是否相等也是不可判定的（这本质上是停止问题）。

你无法判断一个实数 x 是否是有理数：即使在数学中，这通常也很困难，因为你必须找到 p 和 q 使得 x = p/q，而这通常是非建设性的。

然而，给定一个精度窗口，您可以使用连续分数展开等方法找到该精度的“最佳”有理近似值。我相信这本质上就是mathematica 所做的事情。但在你的例子中，6.75 已经是有理数了。尝试用 Pi 代替。