在python中提高无理数的精度

Question

我试图用Python对无理数进行continued fraction derivation，例如sqrt（13）。我已经得到了一个相当好的解决方案，对于前10次左右的迭代是准确的：

1. 将原始数字设置为当前余数
2. 将当前余数的下限追加到系数列表中
3. 将新余数定义为当前余数减去下限的倒数
4. 除非新余数为0，否则转至步骤2

这很好地工作，除了在以后的迭代中，float精度会产生错误的系数。一旦一个系数被关闭，其余的也将自动关闭。在

因此，我的问题是，是否有一种方法来处理无理数，例如sqrt（13），就像占位符（用于以后的替换）一样，还是以更精确的方式处理？在

我目前的代码如下：

import math


def continued_fraction(x, upper_limit=30):
    a = []
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit):
        a.append(int(x))
        x = 1.0/(x - a[-1])
    return a


if __name__ == '__main__':
    print continued_fraction(math.sqrt(13))

结果输出：

^{pr2}$

我知道一个事实，结果输出应该是3，然后是循环（1，1，1，1，6）的无限重复，正如Project Euler Problem 64（我正试图解决这个问题）。在

Answer 1

我不知道Python中有任何这样的占位符。在

但是，您可以考虑使用^{}，这将提高数学运算的精度，但决不能保证循环的无限次重复。为什么？Is floating point math broken?

以下对代码的修改为本次运行提供了正确的结果，直到upper_limit=45：

import math
from decimal import Decimal


def continued_fraction(x, upper_limit=30):
    a = []
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit):
        a.append(int(x))
        x = Decimal(1.0)/(x - a[-1])
    return a


if __name__ == '__main__':
    print (continued_fraction(Decimal(13).sqrt()))

Answer 2

显然，Marius Becceanu发布了an algorithm for the specific continued fraction of sqrt(n)，这是一个迭代，非常好。此算法不需要使用任何浮点。在

Answer 3

你可以看看https://rosettacode.org/wiki/Continued_fraction#Python。它使用分数和Itertools模块。在