Fibonacci, Integer overflow, memoization e um exagero

Let's do an exercise.
Below I leave a code that returns the number in position n of the Fibonacci sequence:

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

How about we try to show in our terminal all the numbers in the Fibonacci sequence smaller than 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);
        }
    }

The problems

When running the code, you will notice two main problems:

• Our loop never ends, and, strangely, negative numbers start to appear in the console.
  

• The code gets slower and slower as time passes.

Problem 1: Negative numbers

Ignore all this Fibonacci stuff for a moment and look at this code.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

How much do you think the result of this will be? 2 billion 2 billion = 4 billion right? So in our code the result will be 4 billion... right?

WRONG!

The way out was actually this:

The reason for this result is overflow. The int type has a maximum limit of 2147483647 (or 2^31 - 1). When this limit is exceeded, the value "returns" to the lowest possible value of type int, which is -2147483648.

Why didn't our loop stop?

Our loop was supposed to stop when we reached a number greater than or equal to 2147483647, but as the Fibonacci values ​​exceeded the int limit, negative numbers started to be generated. Since we never reached a number greater than 2147483647, the loop never stopped.

Solution to problem 1

To keep things simple, I'll just change the return type of our fib function from int to long which has a much larger limit. Our code will look like this:

    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);
        }
    }

Now, with the long type, we can correctly print the Fibonacci numbers up to the largest number smaller than 2147483647.

Solving problem 2: slowness

Have you noticed something yet? Every iteration of our loop, the fib function recalculates all previous numbers in the sequence. In other words, we are repeating unnecessary calculations.

How to avoid unnecessary recalculations? I present to you: Memoization. The memoization technique is a way of saving already calculated results so as not to go through the calculation process again.

Let's implement a HashMap to store the values ​​already found, where the key will be the position and the value is the number itself.

    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);
        }
    }

Beautiful! Now our code runs much faster and we solved our problem.

The exaggeration

Actually, memoization wasn't necessary here. I just wanted to bring this concept to teach. We could simply calculate each Fibonacci number until we finished our condition like this:

    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;
        }
    }

I'm done with the fun, right? Sorry! But at least you learned something new.

---

Article cover by: Gerd Altmann from Pixabay

The above is the detailed content of Fibonacci, Integer overflow, memoization e um exagero. For more information, please follow other related articles on the PHP Chinese website!