Calculando números de Fibonacci grandes com Java

Por
|

O estouro de variável é um possível problema que pode acontecer quando calculamos números de Fibonacci muito grandes. Isto é, o número pode ser grande demais para ser representado utilizando um tipo de dado primitivo.

Espiral de Fibonacci e décimo milésimo número de Fibonacci
Décimo milésimo número de Fibonacci no fundo da imagem

É razoável pensarmos nisso, uma vez que os números de Fibonacci crescem exponencialmente [1].

No caso específico da linguagem de programação Java, podemos driblar esse problema utilizando a classe BigInteger, que permite representar inteiros com precisão arbitrária [3]. Utilizarei essa classe neste artigo.

Algoritmo para calcular números de Fibonacci

Dentre as dezenas de algoritmos para calcular números de Fibonacci, utilizarei o algoritmo logarítmico apresentado em Calculando números de Fibonacci com potenciação de matrizes, pois é o mais eficiente que eu conheço até a data de publicação desta postagem.

Basicamente, vou trocar o tipo de dado primitivo long por BigInteger e substituirei as operações básicas por métodos da classe BigInteger.

Enfim, não tem segredo. O código é dado a seguir

//GitHub: HenriqueIni
import java.math.BigInteger;

//Calcula números de Fibonacci com precisão arbitrária
//O ideal é utilizar esse algoritmo para números muito grandes
public class FibonacciBigInteger {
    //Calcula o n-ésimo número de Fibonacci [O(f(m) log n)]
    public static BigInteger fibonacci(int n){
        if(n < 0){
            throw new IllegalArgumentException("n < 0");
        }
        if(n == 0){
            return BigInteger.ZERO;
        }
        if(n == 1){
            return BigInteger.ONE;
        }
        //Matriz de base
        BigInteger[][] baseMatrix = new BigInteger[][]{
            {BigInteger.ZERO,BigInteger.ONE},
            {BigInteger.ONE,BigInteger.ONE}};        
        BigInteger[][] result = powMatrix2x2(baseMatrix, n);
        return result[0][1];
    }
    
    //Calcula A^n, onde A é uma matrix 2x2 [O(f(m) log n)]
    private static BigInteger[][] powMatrix2x2(BigInteger[][] A, int n){
        //Potenciação por quadrados
        BigInteger[][] p = new BigInteger[][]{
            {BigInteger.ONE,BigInteger.ZERO},
            {BigInteger.ZERO,BigInteger.ONE}};
        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(f(m))]
    private static BigInteger[][] multMatrix2x2(BigInteger[][] A, BigInteger[][] B){
        BigInteger[][] result = new BigInteger[2][2];
        result[0][0] = A[0][0].multiply(B[0][0]).add(A[0][1].multiply(B[1][0]));
        result[0][1] = A[0][0].multiply(B[0][1]).add(A[0][1].multiply(B[1][1]));
        result[1][0] = A[1][0].multiply(B[0][0]).add(A[1][1].multiply(B[1][0]));
        result[1][1] = A[1][0].multiply(B[0][1]).add(A[1][1].multiply(B[1][1]));
        return result;
    }
    
    //Testes
    public static void main(String[]args){
        System.out.println("Fibonacci O(f(m) log n)");
        for(int i = 0; i < 200; i++){
            System.out.printf("F%d = %s\n", i, fibonacci(i).toString());
        }
        //Fibonacci(200.000)
        System.out.printf("F%d = %s\n", 200000, fibonacci(200000).toString());
    }
}

Complexidade assintótica

Se considerarmos que as operações básicas (multiplicações e adições) de BigInteger têm complexidade no tempo constante, então a complexidade do algoritmo anterior será $O(\log n)$.

Mas, infelizmente, não podemos fazer isso... Isto é, o custo das operações básicas deve ser considerado, pois o tamanho dos números é arbitrário: quanto maior o número, mais custosa será a operação.

Nós não precisávamos nos preocupar com isso na versão do código utilizando o tipo long porque os números ocupavam 64 bits de memória fixos, logo a complexidade das operações tinha um limitante superior constante.

O correto é dizer que a complexidade é $O(f(m)\times\log n)$, onde $f(m)$ é uma função que representa o custo das operações de adição e multiplicação para números de tamanho $m$.

O que é esse $m$? Pode ser o tamanho do número em bits, em quantidade de dígitos... Não dá para ser mais específico porque precisaríamos de dados mais precisos sobre o algoritmo que a classe BigInteger utiliza nos cálculos.

Outras linguagens de programação

Se você não utiliza a linguagem de programação Java, então você provavelmente vai precisar de alguma estrutura ou classe para substituir a classe BigInteger no algoritmo.

No caso da linguagem C, você pode utilizar a biblioteca GMP.

Se você utiliza a linguagem Python, então você não precisa se preocupar com o problema de estouro de variável ao calcular números de Fibonacci, pois o Python possui suporte nativo para inteiros de precisão arbitrária. O limite é a memória disponível [2].

Bônus: décimo milésimo número de Fibonacci

A seguir, apresento o décimo milésimo número de Fibonacci, que foi calculado utilizando o programa anterior. Esse número possui 2090 dígitos.

Décimo milésimo número de Fibonacci

Leia também

Referências

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário