连续分数的分数类（支持 1/0）（优化使其变得更糟）

Question

我想快速计算分数，但我还需要支持，其中 1/0 = 无穷大是有效分数。

我做了一个自定义课程

class Frac:
    def __init__(self, num: int, denom=1):
        self.num = num
        self.denom= denom
        self.reduce()

    def reduce(self):
        if self.denom== 0:
            self.num = 1
        else:
            gcd = math.gcd(self.num, self.denom)  #
            gcd *= -1 if self.denom< 0 else 1
            self.num //= gcd
            self.denom//= gcd

    def __add__(self, other):
        return Frac(self.num * other.denom+ other.num * self.denom, self.denom* other.denom)

    def __mul__(self, other):
        return Frac(self.num * other.num, self.denom* other.denom)

    def __truediv__(self, other):
        return self * Frac(self.denom, self.num)

这有效。但我只需要它来计算元组的连续分数， 例如[7,3,6,8] -> 8 + 1 / (6 + 1/ (3 + 1/7))。

@cache
def continued_fraction(f: tuple):
    return Frac(f[-1]) + Frac(1,0) / (continued_fraction(f[:-1])) if len(f) > 1 else Frac(f[-1])

但后来我想为什么我需要一个类来完成这个操作，所以我尝试使用 2 元组来加速它（分数 a/b 表示为 (a,b)）：

def reduce(f):
    if f[1] == 0:
        return (1, 0)
    else:
        gcd = math.gcd(f[0], f[1]) if f[1] >= 0 else -math.gcd(f[0], f[1])
        return f[0] // gcd, f[1] // gcd

@cache
def cont(m, g): # continue fraction, return m + 1 / g
    return reduce((m * g[0] + g[1], g[0]))

@cache
def new_continued_fraction(f: tuple):
    if len(f) == 1:
        return (f[-1], 1)
    return cont(f[-1], new_continued_fraction(f[:-1]))

对于大约500k列表，旧算法需要1.3秒，新算法需要1.9秒。这么大的开销，旧的怎么可能更快呢？

计算列表的连续部分的快速实现是什么？

测试集可以通过以下方式生成：

def generate(n: int):
    yield (n,)
    if n:
        yield (-n,)
    for i in range(1, n + 1):
        for p in generate(n-i):
            yield (i,) + p
            yield (-i,) + p

打电话，例如n = 11.

Answer 1

这似乎比您尝试使用

new_continued_fraction()

更快，但请谨慎对待，因为它不会产生相同的结果。

items = [7,3,6,8]
expected = new_continued_fraction(items)
print(expected[0] / expected[1])

给我

8.158273381294965

，而我的方法给我

8.158227848101266

，如果这不是浮点数学是否损坏？，有人可以指出我有一个错误，这会很酷。如果我有错误，我一定会删除这个答案

def continued_fraction_test(items):
    def recurser(remaining):
        if not remaining:
            return 1
        continuation = recurser(remaining[1:])
        return remaining[0] if not continuation else remaining[0] + 1 / continuation
    return recurser(items[::-1])