Метод возведения в степень быстрой матрицы Фибоначчи - PullRequest
Новая
       88

Метод возведения в степень быстрой матрицы Фибоначчи

0 голосов
/ 06 февраля 2020

Итак, я программировал некоторые программы для вычисления последовательности Фибоначчи, и при поиске решений для ускорения процесса я наткнулся на этот код. 

def fib(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    
            v1, v2, v3 = v1+v2, v1, v2
    return v2
n = int(input())
print(fib(n))

Я знаю, что этот код использует быстрый матричное возведение в степень для нахождения n-го числа Фибоначчи, но я не очень понимаю, почему мы используем двоичную форму числа n, это какой-то трюк программирования, которого я не изучил? Я реализовал матричное возведение в степень с модулем numpy, и, похоже, он делает то же самое. У кого-нибудь есть объяснение бинарной части первой программы, а также почему она, кажется, быстрее вычисляет n-е число Фибоначчи? 

import numpy as np
def fibo(n):
    return (np.matrix([[1, 1], [1, 0]], dtype=object)**(n)).item(1)
n = int(input())
print(fibo(n))
...