Python中的fractions.limit_denominator是如何实现的？

Question

Python中的fractions.limit_denominator是如何实现的？

10

limit_denominator(max_denominator=1000000)
Finds and returns the closest Fraction to self that has denominator at most max_denominator. This method is useful for finding rational approximations to a given floating-point number:

>>>
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)

不应该像尝试a/999、b/998、c/997这样的方法来寻找最佳近似值。

- thkang

1

就我个人而言，作为“Fraction.limit_denominator”的原始作者，一直以来我都很困扰于正确性证明部分存在于我的脑海、零散笔记和在线书籍资源中。最近我需要修改代码，但花费了太长时间去回忆它的工作原理。所以10年后，我终于发布了一个证明：https://github.com/python/cpython/issues/95723 - Mark Dickinson

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kindall · Accepted Answer

< p>

fractions  模块是使用 Python 编写的，您可以查看源代码。它包含以下注释。

    # Algorithm notes: For any real number x, define a *best upper
    # approximation* to x to be a rational number p/q such that:
    #
    #   (1) p/q >= x, and
    #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
    #
    # Define *best lower approximation* similarly.  Then it can be
    # proved that a rational number is a best upper or lower
    # approximation to x if, and only if, it is a convergent or
    # semiconvergent of the (unique shortest) continued fraction
    # associated to x.
    #
    # To find a best rational approximation with denominator <= M,
    # we find the best upper and lower approximations with
    # denominator <= M and take whichever of these is closer to x.
    # In the event of a tie, the bound with smaller denominator is
    # chosen.  If both denominators are equal (which can happen
    # only when max_denominator == 1 and self is midway between
    # two integers) the lower bound---i.e., the floor of self, is
    # taken.