Python 2.7 - 续分数扩展 - 理解错误

Question

我编写了这段代码来计算使用欧几里德算法的有理数N的连续分数展开:

from __future__ import division

def contFract(N):
    while True:
        yield N//1
        f = N - (N//1)
        if f == 0:
            break
        N = 1/f

如果说N是3.245,则函数永远不会结束,因为显然f永远不等于0.扩展的前10个术语是:

[3.0,4.0,12.0,3.0,1.0,247777268231.0,4.0,1.0,2.0,1.0]

这显然是一个错误,因为实际扩展只是:

[3; 4,12,3,1]或[3; 4,12,4]

是什么原因引起了这个问题？这是某种舍入错误吗？

Answer 1

问题是你正在测试f == 0（整数0），这对于浮点数来说几乎从来都不是真的。所以循环会永远持续下去。

相反，检查一些等于 0 的精度（有时可能是错误的）：

>>> from __future__ import division
>>>
>>> def contFract(N):
...     while True:
...         yield N//1
...         f = N - (N//1)
...         if f < 0.0001:  # or whatever precision you consider close enough to 0
...             break
...         N = 1/f
...
>>>
>>> list(contFract(3.245))
[3.0, 4.0, 12.0, 3.0, 1.0]
>>>

如果f可能为负数，请执行-0.0001 < f < 0.0001或abs(f) < 0.0001。这也被认为是不准确的，请参阅链接的文章。

并使用我的评论int(N)而不是N//1因为它更清晰 - 它的效率稍低：

>>> import timeit
>>> timeit.timeit('N = 2.245; N//1', number=10000000)
1.5497028078715456
>>> timeit.timeit('N = 2.245; int(N)', number=10000000)
1.7633858824068103