python - 快速加倍斐波那契 Python 生成器序列

Question

我在尝试使用以下代码创建快速加倍斐波那契 python 生成器时遇到了麻烦。

给定 F(k) 和 F(k+1)，我们可以计算这些:

F(2k) = F(k)[2F(k + 1) − F(k)]
F(2k+1) = F(k+1)^2 + F(k)^2

我有以下最简单(慢)斐波那契生成器:

def fib_generator():
    n = 1
    n0 = 1
    while True:
        yield n
        n, n0 = n + n0, n

Answer 1

实现可以是:

from itertools import count

def fast_fib_generator():
    F = [1, 1]
    yield 1
    yield 1
    for k in count(1):
        F.append(F[k] ** 2 + F[k - 1] ** 2)
        yield F[-1]

        F.append(F[k] * (2 * F[k + 1] - F[k]))
        yield F[-1]


for x in fast_fib_generator():
    print x

第一个结果:

1
1
2
3
5
8
13
21
34