Формула прямого расчета Фибоначчи

Question

Я видел, что у Фибоначчи есть прямая формула с этим (Phi^n)/√5, в то время как я получаю результаты в одно и то же время, но точный результат не приблизился к чему-то, что мне удалось написать:

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

(! - этосимвол для факториал ):

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

Я не понимаю, почему(n-r)!/((n-2r)!r!) быстро

Answer 1

Формула Бине для n-го числа Фибоначчи выглядит следующим образом:

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

Эта формула математически точна, но на практике она подвержена ошибкам с плавающей запятой.Член psi ** n быстро сходится к нулю при увеличении n, поэтому его можно опустить, если n велико.Это дает приблизительную формулу.

Формула Бине очень быстрая.На моей машине он вычисляет тысячное число Фибоначчи примерно за 400 наносекунд.

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

Формула биномиальной суммы для чисел Фибоначчи очень интересна.Это говорит о том, что числа Фибоначчи являются суммами вдоль мелких диагоналей треугольника Паскаля, как показано на этом рисунке.

Эта формула работает, потому что каждая диагональ является суммой двух предыдущих диагоналей, так же, как каждый член в последовательности Фибоначчи является суммой двух предыдущих членов.Например, для получения одиннадцатой диагонали можно добавить девятую и десятую диагонали.

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

Однако эта формула не является быстрой.Это кажется быстрым, потому что компьютеры могут выполнять миллионы вычислений в секунду.Моей машине нужно 84 мс, чтобы вычислить тысячное число Фибоначчи, используя ваш код.Это в 200 000 раз дольше, чем по формуле Бине.

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