Эффективный алгоритм для вычисления

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

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

- го числа Фибоначчи также может быть вычислена как [ ф п / $n$. Тем не менее, это имеет проблемы с проблемами округления даже для относительно небольшихn. Наверное, естьспособы обойти это,но я бы не стал этого делать.$\left[\varphi^n / \sqrt{5}\right]$$n$

Существует ли эффективный (логарифмический по значению или лучше) алгоритм для вычисления n- го числа Фибоначчи, которое не зависит от арифметики с плавающей запятой? Предположим, что целочисленные операции ( + , - , × , / ) могут выполняться за постоянное время.$n$$n$$+$$-$$\times$$/$

Вы можете использовать матричное питание и тождество В вашей модели вычислений это алгоритм O ( log n ) , если вы используете многократное возведение в квадрат для реализации питания.

Вы можете прочитать эту математическую статью: Быстрый алгоритм для вычисления больших чисел Фибоначчи (Daisuke Takahashi): PDF .

Проще говоря, я реализовал несколько алгоритмов Фибоначчи на C ++ (без и с GMP) и Python. Полные источники на Bitbucket. На главной странице вы также можете перейти по ссылкам на:

• C ++ HTML онлайн документация.
• Небольшой математический документ: числа Фибоначчи - несколько отношений для реализации хороших алгоритмов

Наиболее полезные формулы:

• $F_{2n} = F^2_{n + 1} - F^2_{n - 1} = 2 F_n F_{n - 1} + F^2_n$
• $F_{2n + 1} = F^2_{n + 1} + F^2_n$

Будьте осторожны с алгоритмом. Вы не должны вычислять одно и то же значение несколько раз. Простой рекурсивный алгоритм (в Python):

def fibonacci_pair(n):
    """Return (F_{n-1}, F_n)"""
    if n != 0:
        f_k_1, f_k = fibonacci_pair(n//2)  # F_{k-1},F_k with k = n/2

        return ((f_k**2 + f_k_1**2,
                 ((f_k*f_k_1)*2) + f_k**2) if n & 1 == 0  # even
                else (((f_k*f_k_1)*2) + f_k**2,
                      (f_k + f_k_1)**2 + f_k**2))
    else:
        return (1, 0)

$O(\log n)$

$O(\log_2 n)$

Проверьте бесплатную книгу Matters Computational и pari / gp code.