Calculando números de Fibonacci com potenciação de matrizes

Dentre os diversos algoritmos criados para calcular números da sequência de Fibonacci, alguns deles utilizam a potenciação de matrizes nos cálculos.

Neste artigo, apresento um desses algoritmos e algumas implementações.

A principal vantagem do algoritmo é a possibilidade de calcular números de Fibonacci em tempo $O(\log n)$.

Matriz de base

O algoritmo que irei apresentar consiste em calcular as potências da seguinte matriz 2×2, que chamarei de matriz de base

$$A=\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}$$

Vamos utilizar a notação F_i para denotar o i-ésimo número de Fibonacci:

F₀ = 0
F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3

Observe que o zero será o primeiro número da sequência.

Voltando à matriz de base, vamos calcular algumas de suas potências

$$\begin{align*}\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^2&=\begin{bmatrix}1 & 1\\1 & 2\end{bmatrix}= \begin{bmatrix}F_1 & F_2\\F_2 & F_3\end{bmatrix}\\\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^3&=\begin{bmatrix}1 & 2\\2 & 3\end{bmatrix}= \begin{bmatrix}F_2 & F_3\\F_3 & F_4\end{bmatrix}\\\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^4&=\begin{bmatrix}2 & 3\\3&5\end{bmatrix}= \begin{bmatrix}F_3 & F_4\\F_4 & F_5\end{bmatrix}\\\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^5&=\begin{bmatrix}3 & 5\\5 & 8\end{bmatrix}= \begin{bmatrix}F_4 &F_5\\F_5 & F_6\end{bmatrix}\end{align*}$$

Generalizando, temos

$$\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}^n=\begin{bmatrix}F_{n-1} & F_n\\F_n & F_{n+1}\end{bmatrix}\quad (1)$$

Ou seja, se quisermos calcular o n-ésimo número da sequência de Fibonacci, podemos calcular a n-ésima potência da matriz de base e obter o elemento $a_{12}$ ou $a_{21}$ do resultado (também podemos elevar a matriz à (n-1)-ésima potência e obter o elemento $a_{22}$, que é um pouco mais eficaz).

Escrevendo o algoritmo

Agora que temos a fórmula (1), precisamos de um algoritmo para calcular as potências da matriz de base.

No artigo Potenciação de Matrizes, apresento dois algoritmos de potenciação de matrizes, sendo que um deles tem complexidade $O(f(m)n)$ e o outro tem complexidade $O(f(m)\log n)$, onde $f(m)$ é o custo da multiplicação entre matrizes de ordem m.

Como a matriz de base é de ordem 2, então o custo da multiplicação será constante.

Portanto, se escolhermos o primeiro algoritmo de potenciação, então a complexidade final será $O(n)$. Se optarmos pelo segundo algoritmo, então a complexidade final será $O(\log n)$, que é mais eficiente.

Independente da sua escolha, o algoritmo em pseudocódigo será:

1. fib(n)
2.    A ← |0 1|
          |1 1|
3.    R ← power(A, n)
4.    retorne R(1, 2)
5. fim_fib

No algoritmo anterior, A é a matriz de base, power é o algoritmo de potenciação escolhido, R é o resultado da potenciação e R(1, 2) é o elemento da linha 1 e coluna 2 de R.

Códigos

A seguir, apresento a implementação das duas versões do algoritmo em Java e em C.

A potenciação de matrizes implementada foi otimizada para matrizes 2×2.

Algoritmo linear O(n)

Em Java:

//GitHub: HenriqueIni
public class FibonacciMatrixLin {
    //Calcula o n-ésimo número de Fibonacci [O(n)]
    public static long fibonacci(int n) {
        if (n < 2) return n;
        long[][] baseMatrix = {{0, 1}, {1, 1}};
        long[][] result = powMatrix2x2(baseMatrix, n);
        return result[0][1];
    }
    
    //Calcula A^n, onde A é uma matrix 2x2 [O(n)]
    private static long[][] powMatrix2x2(long[][] A, int n) {
        //Potenciação Linear
        long[][] p = {{1, 0}, {0, 1}};
        for(int i = 0; i < n; i++){
            p = multMatrix2x2(p, A);
        }
        return p;
    }

    //Calcula A*B, onde A e B são matrizes 2x2 [O(1)]
    private static long[][] multMatrix2x2(long[][] A, long[][] B) {
        return new long[][]{{A[0][0] * B[0][0] + A[0][1] * B[1][0],
                             A[0][0] * B[0][1] + A[0][1] * B[1][1]},
                            {A[1][0] * B[0][0] + A[1][1] * B[1][0],
                             A[1][0] * B[0][1] + A[1][1] * B[1][1]}};
    }

    //Testes
    public static void main(String[] args) {
        System.out.println("Fibonacci O(n)");
        for (int i = 0; i < 20; i++) {
            System.out.printf("F%d = %d\n", i, fibonacci(i));
        }
    }
}

Em C:

//GitHub: HenriqueIni
#include <stdio.h>
#include <stdlib.h>

//'Gambiarra' para multiplicar matrizes 2x2, R = A * B
void matrixMult2x2(long A[2][2], long B[2][2], long R[2][2]){
    long temp[2][2]; //Armazena temporariamente os resultados
    temp[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
    temp[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1];
    temp[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
    temp[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1];
    //Passa os resultados para R
    R[0][0] = temp[0][0];
    R[0][1] = temp[0][1];
    R[1][0] = temp[1][0];
    R[1][1] = temp[1][1];
}

//Calcula o n-ésimo número de Fibonacci [O(n)]
long fibonacciLin(int n){
    if(n < 2){
        return n;
    }
    //Matriz de base
    long baseMatrix[2][2] = {{0,1},{1,1}};
    
    //Potenciação linear
    long p[2][2] = {{1, 0}, {0, 1}};
    int i;
    for(i = 0; i < n; i++){        
        matrixMult2x2(p, baseMatrix, p);
    }
    return p[0][1];
}

//Testes
int main() {
    //Testa o algoritmo O(n)
    printf("\nFibonacci O(n)\n");    
    for(i = 0; i < 20; i++){
        printf("F%d = %d\n", i, fibonacciLin(i));
    }
    return 0;
}

Algoritmo logarítmico O(log n)

Em Java:

//GitHub: HenriqueIni
public class FibonacciMatrixLog {
    //Calcula o n-ésimo número de Fibonacci [O(log n)]
    public static long fibonacci(int n){
        if(n < 2) return n;        
        long[][] baseMatrix = {{0,1},{1,1}};        
        long[][] result = powMatrix2x2(baseMatrix, n);
        return result[0][1];
    }
    
    //Calcula A^n, onde A é uma matrix 2x2 [O(log n)]
    private static long[][] powMatrix2x2(long[][] A, int n){
        //Potenciação por quadrados
        long[][] p = {{1,0},{0,1}};
        while(n > 0){
            if((n % 2) != 0)
                p = multMatrix2x2(p, A);
            A = multMatrix2x2(A, A);
            n = n / 2;
        }
        return p;
    }
    
    //Calcula A*B, onde A e B são matrizes 2x2 [O(1)]
    private static long[][] multMatrix2x2(long[][] A, long[][] B){
        return new long[][]{{A[0][0] * B[0][0] + A[0][1] * B[1][0],
                             A[0][0] * B[0][1] + A[0][1] * B[1][1]},
                            {A[1][0] * B[0][0] + A[1][1] * B[1][0],
                             A[1][0] * B[0][1] + A[1][1] * B[1][1]}};
    }
    
    //Testes
    public static void main(String[]args){
        System.out.println("Fibonacci O(log n)");
        for(int i = 0; i < 20; i++){
            System.out.printf("F%d = %d\n", i, fibonacci(i));
        }        
    }
}

Em C:

//GitHub: HenriqueIni
#include <stdio.h>
#include <stdlib.h>

//'Gambiarra' para multiplicar matrizes 2x2, R = A * B
void matrixMult2x2(long A[2][2], long B[2][2], long R[2][2]){
    long temp[2][2]; //Armazena temporariamente os resultados
    temp[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
    temp[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1];
    temp[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
    temp[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1];
    //Passa os resultados para R
    R[0][0] = temp[0][0];
    R[0][1] = temp[0][1];
    R[1][0] = temp[1][0];
    R[1][1] = temp[1][1];
}

//Calcula o n-ésimo número de Fibonacci [O(log n)]
long fibonacciLog(int n){
    if(n < 2){
        return n;
    }
    //Matriz de base
    long baseMatrix[2][2] = {{0,1},{1,1}};
    
    //Potenciação por quadrados
    long p[2][2] = {{1,0}, {0,1}};    
    while(n > 0){
        if((n % 2) != 0){
            matrixMult2x2(p, baseMatrix, p);
        }        
        matrixMult2x2(baseMatrix, baseMatrix, baseMatrix);
        n = n / 2;
    }
    return p[0][1];
}

//Testes
int main() {
    //Testa o algoritmo O(log n)
    printf("Fibonacci O(log n)\n");
    int i;
    for(i = 0; i < 20; i++){
        printf("F%d = %d\n", i, fibonacciLog(i));
    }
    return 0;
}

Referências

GeeksforGeeks: Program for Fibonacci numbers. Acesso em 13 de abril de 2018.

Calculando números de Fibonacci com potenciação de matrizes

Matriz de base

Escrevendo o algoritmo

Códigos

Algoritmo linear O(n)

Algoritmo logarítmico O(log n)

Referências

Siga o blog

Nenhum comentário:

Postar um comentário

Como obter o ID de um canal do YouTube?

Potenciação de Matrizes

Questões Resolvidas do ENADE 2017 de Ciência da Computação

Teorema Mestre e Exemplos Resolvidos

Quicksort (análise e implementações)

Algoritmo para calcular o MMC