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.
É 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.
Leia também
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.
Nenhum comentário:
Postar um comentário