Vamos fazer um exercício.
Abaixo deixo um código que retorna o número na posição n da sequência de Fibonacci:
public static int fib(int n){
if (n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
Que tal tentarmos mostrar no nosso terminal todos os números da sequência de fibonacci menores que 2147483647?
public static int fib(int n){
if (n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int position = 1;
int currentNumber = fib(position);
while (currentNumber < 2147483647) {
System.out.println(currentNumber);
position++;
currentNumber = fib(position);
}
}
Os problemas
Ao executar o código, você vai perceber dois problemas principais:
Nosso loop nunca termina, e, estranhamente, números negativos passam a aparecer no console.
O código fica cada vez mais lento conforme o tempo passa.
Problema 1: Os números negativos
Ignora por um momento toda essa história de fibonacci e olhe esse código.
public static void main(String[] args) {
int a = 2_000_000_000;
int b = 2_000_000_000;
System.out.println(a + b);
}
Quanto você acha que vai ser o resultado disso? 2 bilhões + 2 bilhões = 4 bilhões certo? Então no nosso código o resultado vai ser 4 bilhões... certo?
ERRADO!
A saída na verdade foi essa:
O motivo para esse resultado é o overflow. O tipo int tem um limite máximo de 2147483647 (ou 2^31 - 1). Quando esse limite é ultrapassado, o valor "retorna" ao menor valor possível do tipo int, que é -2147483648.
Por que nosso loop não parou?
Nosso loop deveria parar quando chegássemos a um número maior ou igual a 2147483647, mas como os valores de Fibonacci ultrapassaram o limite de int, números negativos começaram a ser gerados. Como nunca chegamos a um número maior que 2147483647, o loop nunca parou.
Solução para o problema 1
Pra manter as coisas simples, eu apenas mudarei o tipo de retorno da nossa função fib de int pra long que tem um limite muito maior. Nosso código ficará assim:
public static long fib(long n){
if (n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
long position = 1;
long currentNumber = fib(position);
while (currentNumber < Integer.MAX_VALUE) {
System.out.println(currentNumber);
position++;
currentNumber = fib(position);
}
}
Agora, com o tipo long, conseguimos imprimir corretamente os números do Fibonacci até o maior número menor que 2147483647.
Resolvendo o problema 2: lentidão
Já percebeu uma coisa? Toda iteração do nosso loop a função fib recalcula todos os números anteriores da sequência. Ou seja, estamos repetindo cálculos desnecessários.
Como evitar recálculos desnecessários? Apresento-lhes: Memoization. A técnica de memoization é uma forma de guardar resultados já calculados para não passar novamente pelo processo de cálculo.
Vamos implementar um HashMap para guardar os valores já encontrados, onde a chave será a posição e o valor é o próprio número.
static HashMap<Long, Long> memo = new HashMap<>();
public static long fib(long n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 1) {
return n;
}
long result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
long position = 1;
long currentNumber = fib(position);
while (currentNumber < 2147483647) {
System.out.println(currentNumber);
position++;
currentNumber = fib(position);
}
}
Lindo! Agora nosso código roda muuito mais rápido e resolvemos nosso problema.
O exagero
Na verdade, memoization não era necessário aqui. Eu só quis trazer para ensinar esse conceito. Nós podíamos simplesmente calcular cada número do Fibonacci até acabarmos nossa condição dessa forma:
public static void main(String[] args) {
long prev1 = 0;
long prev2 = 1;
long current;
System.out.println(prev1);
while (prev2 < 2147483647) {
System.out.println(prev2);
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
}
Acabei com a graça né? Desculpa! Mas espero que tenha aprendido algo novo.
Capa do artigo por: Gerd Altmann do Pixabay
Top comments (1)
Brabo