斐波那契直接计算公式 [英] Fibonacci direct calculation formula

问题描述

我已经看到斐波那契对此具有直接公式(Phi^n)/√5 虽然我同时获得结果，但是准确的结果与我设法写的东西不相近:

I have seen Fibonacci has direct formula with this (Phi^n)/√5 while I am getting results in same time but accurate result not approximate with something I managed to write:

for r = 0 to 2 Sum [(n-r)!/((n-2r)!r!)] 

(!是 factorial 的符号):

def fr(n, p):
    # (n-r)!/((n-2r)!r!)
    r = int(n / p)
    n_f = 0
    for j in range(1, r + 1):
        t_f = 1
        r_f = factorial(j)
        i = (n - j)

        while i > (n - (2 * j)):
            t_f = t_f * i
            i = i - 1

        n_f = n_f + t_f / r_f

    return n_f + 1

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

所以我们可以做12个fr(11, 2) 也将(Phi12)/√5 = 144.0013888754932舍入为Fib(12) =144

so for 12 we can do fr(11, 2) also (Phi12)/√5 = 144.0013888754932 rounds to Fib(12) =144

我不明白为什么(n-r)!/((n-2r)!r!)快速

推荐答案

第n个斐波那契数的Binet公式如下:

Binet's formula for the nth Fibonacci number is as follows:

def binet(n):
    phi = (1 + 5**.5) / 2
    psi = (1 - 5**.5) / 2
    return (phi**n - psi**n) / 5**.5

该公式在数学上是精确的，但在实践中会遇到浮点误差.术语psi ** n随着n的增加而迅速收敛到零，因此当n大时可以省略.这将得出您的近似公式.

This formula is mathematically exact, but in practice it is subject to floating point error. The term psi**n converges rapidly to zero as n increases, so it can be omitted when n is large. This yields your approximate formula.

Binet的公式非常快.在我的机器上，它可以在大约400纳秒内计算出第1000个斐波那契数.

Binet's formula is very fast. On my machine, it computes the 1000th Fibonacci number in about 400 nanoseconds.

In [21]: %timeit binet(1000)
426 ns ± 24.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

斐波纳契数的二项式和公式非常有趣.它说斐波纳契数是沿着Pascal三角形的浅对角线的和，如图所示.

The binomial sum formula for Fibonacci numbers is very interesting. It says that Fibonacci numbers are sums along shallow diagonals of Pascal's triangle, as shown in this figure.

该公式之所以有效，是因为每个对角线是前两个对角线的和，就像斐波那契数列中的每个项都是前两个对角线的和一样.例如，可以添加第九和第十对角线以获得第十一对角线.

This formula works because each diagonal is the sum of the two previous diagonals, just as every term in the Fibonacci sequence is the sum of the two previous terms. For example, the ninth and tenth diagonals can be added to obtain the eleventh diagonal.

    1 +  7 + 15 + 10 + 1 = 34
1 + 8 + 21 + 20 +  5     = 55
-----------------------------
1 + 9 + 28 + 35 + 15 + 1 = 89

但是，这个公式根本不是很快.它看起来很快速，因为计算机每秒可以执行数百万次计算.我的机器需要84毫秒才能使用您的代码计算第1000个斐波那契数.这比使用Binet公式所需的时间长200,000倍.

However, this formula is not fast at all. It seems fast because computers can perform millions of calculations per second. My machine needs 84 ms to calculate the 1000th Fibonacci number using your code. This is 200,000 times longer than it takes using Binet's formula.

 In [22]: %timeit fr(1001, 2)
 84 ms ± 875 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

这篇关于斐波那契直接计算公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！