Необходимо найти n-ый член последовательности , если: $F_{0}= 0$, $F_{1}= 1$, $F_{n}= F_{n-1}+ F_{n-2}$, где $n\geq2$, $n \in Z$

Существует способ нахождения чисел Фибоначчи через матрицу за O(logN). Но для него необходимо уметь быстро возводить матрицу в степень

Обычное возведение в степень вычисляется за O(n) по рекуррентной формуле $X^{n}= X^{n-1}* X$:

Но количество операций можно значительно уменьшить, если воспользоваться другой рекуррентной формулой $X^{n}= X^{n/2}* X^{n/2}$:

Если степень нечётная, то формула немного изменится: $X^{n}=X^{(n-1)}*X = X^{(n-1)/2}* X^{(n-1)/2}*X$. Это называется бинарным возведением в степень, которое работает за O(logN).

Псевдокод:

//X - число, возводимое в степень
//n - степень, в которое возводится число

функция бинарное_возведение_в_степень(X, n):
    если n = 0, то 
        вернуть 1
    если n = 1, то 
        вернуть X
    если n не кратно 2, то 
        вернуть бинарное_возмедение_в_степень(X, n-1)*X
    если n кратно 2, то 
        вернуть бинарное_возмедение_в_степень(X, n/2)^2

#python

def bin_pow(x, n):
    if -1 < x < 0 or 0 < x < 1:
        return -1
    if n < 0:
        return -1
    if n == 0:
        return 1
    if n == 1:
        return x
    if n % 2 != 0:
        return bin_pow(x, n - 1) * x
    if n % 2 == 0:
        return bin_pow(x, n//2) * bin_pow(x, n//2)

//C++
//sport version

int bin_pow(int x, int n){
    if(n < 0){
        return -1;
    }
    if(n == 0){
        return 1;
    }
    if(n == 1){
        return x;
    }
    if(n % 2 != 0){
        return bin_pow(x, n - 1) * x;
    }
    if(n % 2 == 0){
        return bin_pow(x, n/2) * bin_pow(x, n/2);
    }
}

//C++
//production version

template<typename ValueType>
ValueType bin_pow(ValueType x, ValueType n){
    if (-1 < x < 0 or 0 < x < 1){
        return -1;
    }
    if(n < 0){
        return -1;
    }
    if(n == 0){
        return 1;
    }
    if(n == 1){
        return x;
    }
    if(n % 2 != 0){
        return bin_pow(x, n - 1) * x;
    }
    if(n % 2 == 0){
        return bin_pow(x, n/2) * bin_pow(x, n/2);
    }
}

Для чисел Фибоначчи верно следующее равенство: $\left(\begin{array}{cccc} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{array} \right) = \left(\begin{array}{cccc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n}_{*}$ То есть $F_{n} = \left(\begin{array}{cccc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n-1}[0][0])$. В степень матрицу можно возвести за O(logN), а значит и найти n-ое число Фибоначчи:

Псевдокод:

//n - искомое число Фибоначчи
//bin_matrix - матрица, полученная бинарным возведением в степень

функция фибоначчи_через_матрицу(n):
    если n < 0, то
        вернуть -1
    если n = 0, то 
        вернуть 0
    bin_matrix <- воздённая в степень (n-1) матрица *
    n-ое число Фибоначчи <- bin_matrix[0][0]
    вернуть n-ое число Фибоначчи

#python

class FibMatrix:

    def __init__(self, n):
        self.n = n
    
    def fib_matrix(self):
        matrix = [[1 for _ in range(2)] for _ in range(2)]
        matrix[1][1] = 0
        if self.n < 0:
            return -1
        if self.n == 0:
            return 0
        if self.n == 1:
            return 1
        bin_matrix = self.bin_pow_matrix(matrix, self.n - 1)
        fib = bin_matrix[0][0]
        return fib
    
    def bin_pow_matrix(self, matrix, n):
        if n == 1:
            return matrix
        
        if n % 2 != 0:
            temp_matrix = self.bin_pow_matrix(matrix, n - 1)
            return self.prod_matrix(temp_matrix, matrix)
        
        if n % 2 == 0:
            temp_matrix = self.bin_pow_matrix(matrix, n // 2)
            
            return self.prod_matrix(temp_matrix, temp_matrix)

    def prod_matrix(self, a, b):
        matrix_prod = [[0 for _ in range(2)] for _ in range(2)]
        for i in range(2):
            for j in range(2):
                for r in range(2):
                    matrix_prod[i][j] += a[i][r] * b[r][j]
           
        return matrix_prod

//C++
//sport version

vector<vector<int>> prod_matrix(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    vector<vector<int>> m_prod(2, vector<int>(2, 0));
    m_prod[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    m_prod[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    m_prod[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    m_prod[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return m_prod;
}

vector<vector<int>> bin_pow_matrix(const vector<vector<int>>& m, int n) {
    if (n == 1) {
        return m;
    }

    if (n % 2 != 0) {
        vector<vector<int>> temp_m = bin_pow_matrix(m, n - 1);
        return prod_matrix(temp_m, m);
    }

    if (n % 2 == 0) {
        vector<vector<int>> temp_m = bin_pow_matrix(m, n / 2);
        return prod_matrix(temp_m, temp_m);
    }
}

int fib_matrix(int n) {
    vector<vector<int>> m(2, vector<int>(2, 1));
    m[1][1] = 0;
    if (n < 0) {
        return -1;
    }
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    vector<vector<int>> bin_matrix = bin_pow_matrix(m, n - 1);
    int fib = bin_matrix[0][0];
    return fib;
}

//C++
//production version

template<typename ValueType>
vector<std::vector<ValueType>> prod_matrix(const vector<std::vector<ValueType>> &a, const vector<std::vector<ValueType>> &b) {
    std::vector<std::vector<ValueType>> matrix_prod(2, std::vector<ValueType>(2, 0));
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            for (int r = 0; r < 2; r ++){
                matrix_prod[i][j] += a[i][r] * b[r][j];
            }
        }
    }
    
    return matrix_prod;
}

template<typename ValueType>
std::vector<std::vector<ValueType>> bin_pow_matrix(const std::vector<std::vector<ValueType>>& matrix,ValueType n) {
    if (n == 1) {
        return matrix;
    }
    
    if (n % 2 != 0) {
        std::vector<std::vector<ValueType>> temp_matrix = bin_pow_matrix(matrix, n - 1);
        return prod_matrix(temp_matrix, matrix);
    }
    
    if (n % 2 == 0) {
        std::vector<std::vector<ValueType>> temp_matrix = bin_pow_matrix(matrix, n / 2);
        return prod_matrix(temp_matrix, temp_matrix);
    }
}

template<typename ValueType>
ValueType fibonacci_matrix(ValueType n) {
    std::vector<std::vector<ValueType>> matrix(2, std::vector<ValueType>(2, 1));
    matrix[1][1] = 0;
    
    if (n < 0) {
        return -1;
    }
    
    if (n == 0) {
        return 0;
    }
    
    if (n == 1) {
        return 1;
    }
    
    std::vector<std::vector<ValueType>> bin_matrix = bin_pow_matrix(matrix, n - 1);
    ValueType fib = bin_matrix[0][0];
    
    return fib;
}