快速倍增fibonaccipython生成器序列

Question

我在尝试创建一个快速加倍的fibonaccipython生成器时遇到了一些困难，使用以下代码。在

给定F（k）和F（k+1），我们可以计算：

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

下面是最简单（慢）斐波那契生成器：

^{pr2}$

Answer 1

def fibonacci(number):
    numbers = [0, 1]
    while len(numbers) < number:
        numbers[len(numbers):len(numbers)] = [numbers[len(numbers)-2] + numbers[len(numbers)-1]]
    return numbers

首先得到一个fibonacci序列的列表。。。然后循环。在

^{pr2}$

Answer 2

实现可以是：

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

初步结果：

^{pr2}$