在 python 中提高无理数的精度

Question

我正在尝试做一个 continued fraction derivation 无理数，例如sqrt(13)，Python。我已经获得了一个非常好的解决方案，它在前 10 次左右的迭代中是准确的：

将原数设为当前余数
将当前余数的底数附加到系数列表
将新余数定义为当前余数减去底限的倒数
除非新余数为 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))

结果输出：

[3, 1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 7, 2, 1, 4, 2]

我知道一个事实，结果输出应该是 3，然后是循环的无限重复（1、1、1、1、6），根据 Project Euler Problem 64（我'我正在尝试解决）。

Answer 1

我不知道 Python 中有任何此类占位符。

不过，您可以考虑使用 decimal.Decimal which will increase the precision of your math operations but will never guarantee infinite repetitions of the cycle. Why? 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

你可能会把目光投向https://rosettacode.org/wiki/Continued_fraction#Python。它使用 Fractions 和 Itertools 模块。

Answer 3

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

在 python 中提高无理数的精度

Working with increased precision of irrational numbers in python

python

precision