如何在不生成整数的情况下找到第一个k数字的斐波那契数？

Question

我必须找到所有Fibonacci数的第一个k数字，直到fibonacci序列2 * 10 ^ 6。

很明显，我们不能将斐波纳契数的值存储在任何变量中。即使计算所有斐波那契数本身也需要大量的计算时间。那么，有没有办法只获得斐波纳契数的第一个k位数而不产生整数？

Answer 1

由于您只需要前导数字，因此Fibonacci数的近似就足够了。因此，您可以使用闭合形式的公式来表示第n个Fibonacci数

Fn =（φn - （ - φ）-n）/√5，其中φ=（1 +√5）/ 2＆amp; 1.6180339887

...然后四舍五入到所需的精度。

Answer 2

这是一种不会产生所有数字的方法。当谈到快速找到斐波纳契数时，有一个O(k log n)程序，其中O(k)是F(n)与F(n-1)相乘所需的时间。它利用了F(n)恰好是矩阵a[0][1]的a元素的事实，这是简单矩阵n-th [[1, 1], [1, 0]]的(reference)力量。所以你可以使用exponentiation by squaring。这是一个示例python实现：

def matrix_mult(a, b):
    return ((a[0][0]*b[0][0] + a[0][1]*b[1][0], 
             a[0][0]*b[0][1] + a[0][1]*b[1][1]),
            (a[1][0]*b[0][0] + a[1][1]*b[1][0], 
             a[1][0]*b[0][1] + a[1][1]*b[1][1]))


def matrix_pow(a, k):
    if k == 0:
        return ((1, 0), (0, 1))
    t = matrix_pow(a, k//2)
    t2 = matrix_mult(t, t)
    if k % 2 == 0:
        return t2
    return matrix_mult(t2, a)


def fib(n):
    a = ((1, 1), (1, 0))
    return matrix_pow(a, n)[0][1]


def get_first_k(n, k):
    return str(fib(n))[:k]

for n in range(10 ** 2, 10 ** 2 + 10):
    print(get_first_k(n, 3))

#output
#first 3 digits   actual number
354               #354224848179261915075
573               #573147844013817084101
927               #927372692193078999176
150               #1500520536206896083277
242               #2427893228399975082453
392               #3928413764606871165730
635               #6356306993006846248183
102               #10284720757613717413913
166               #16641027750620563662096
269               #26925748508234281076009

对于qazxsw poi，它需要围绕qazxsw poi计算qazxsw poi，考虑到问题的本质，这是合理的。

这是Java替代方案

n = 2 * 10 ** 5