Calculando números de Fibonacci grandes com Java

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.

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

//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

• Fatorial em Java utilizando BigInteger
• A Sequência de Fibonacci: algoritmos em Java e C
• Calculando números de Fibonacci com potenciação de matrizes

Referências

• [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
• [2] PEP 237 -- Unifying Long Integers and Integers. Acesso em 15 de abril de 2018.
• [3] Java DOC: Class BigInteger. Acesso em 15 de abril de 2018.