Fibonacci, Integer overflow, memoization e um exagero

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 < 2147483647) {
            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 pelo menos tu aprendeu algo novo.

Capa do artigo por: Gerd Altmann do Pixabay