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 



<p>How about we try to show in our terminal all the numbers in the Fibonacci sequence smaller than 2147483647?<br>
</p>

<pre class="brush:php;toolbar:false">    public static int fib(int n){
       if (n 



<h2>
  
  
  The problems
</h2>

<p>When running the code, you will notice two main problems:</p>

• 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 



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

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172868455085429.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Fibonacci, Integer overflow, memoization e um exagero"></p>

<h2>
  
  
  Solving problem 2: slowness
</h2>

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

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

<p>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.<br>
</p>

<pre class="brush:php;toolbar:false">
    static HashMap<long long> memo = new HashMap();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n 



<p>Beautiful! Now our code runs much faster and we solved our problem.</p>

<h2>
  
  
  The exaggeration
</h2>

<p>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:<br>
</p>

<pre class="brush:php;toolbar:false">    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 



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


<hr>

<p>Article cover by: Gerd Altmann from Pixabay</p>


          

            
        

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!