title: Making Fibonacci faster
body: <p>I was required to write a simple implementation of Fibonacci's algorithm and then to <strong>make it faster</strong>.</p>
  
  <p>Here is my initial implementation</p>
  
  <pre><code>public class Fibonacci {
  
      public static long getFibonacciOf(long n) {
          if (n== 0) {
              return 0;
          } else if (n == 1) {
              return 1;
          } else {
              return getFibonacciOf(n-2) + getFibonacciOf(n-1);
          }
      }
  
      public static void main(String[] args) {
          Scanner scanner = new Scanner (System.in);
          while (true) {
              System.out.println("Enter n :");
              long n = scanner.nextLong();
              if (n &gt;= 0) {
                  long beginTime = System.currentTimeMillis();
                  long fibo = getFibonacciOf(n);
                  long endTime = System.currentTimeMillis();
  
                  long delta = endTime - beginTime;
  
                  System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
              } else {
                  break;
  
              }
          }
  
      }
  
  }
  </code></pre>
  
  <p>As you can see I am using System.currentTimeMillis() to get a simple measure of the time elapsed while computed Fibonacci.</p>
  
  <p><strong>This implementation get rapidly kind of exponentially slow</strong> as you can see on the following picture</p>
  
  <p><img src="https://i.stack.imgur.com/oziv4.png" alt="simple version of fibonacci&#39;s algorithm"></p>
  
  <p>So <strong>I've got a simple optimisation idea. To put previous values in a HashMap and instead of re-computing them each time, to simply take them back from the HashMap if they exist. If they don't exist, we then put them in the HashMap</strong>.</p>
  
  <p>Here is the new version of the code</p>
  
  <pre><code>public class FasterFibonacci {
  
      private static Map&lt;Long, Long&gt; previousValuesHolder;
      static {
          previousValuesHolder = new HashMap&lt;Long, Long&gt;();
          previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
          previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
      }
      public static long getFibonacciOf(long n) {
          if (n== 0) {
  
              return 0;
          } else if (n == 1) {
              return 1;
          } else {
              if (previousValuesHolder.containsKey(Long.valueOf(n))) {
                  return previousValuesHolder.get(n);
              } {
  
                  long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
                  previousValuesHolder.put(Long.valueOf(n),     Long.valueOf(newValue));
                  return newValue;
              }
  
          }
      }
  
      public static void main(String[] args) {
          Scanner scanner = new Scanner (System.in);
          while (true) {
              System.out.println("Enter n :");
              long n = scanner.nextLong();
              if (n &gt;= 0) {
                  long beginTime = System.currentTimeMillis();
                  long fibo = getFibonacciOf(n);
                  long endTime = System.currentTimeMillis();
  
                  long delta = endTime - beginTime;
  
                  System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
              } else {
                  break;
  
              }
          }
  
      }
  </code></pre>
  
  <p>This change makes the computing extremely fast. I computes all the values from 2 to 103 in no time at all and I get a <strong>long</strong> overflow at F(104) (<strong>Gives me F(104) = -7076989329685730859, which is wrong</strong>).  I find it so fast that **I wonder if there is any mistakes in my code (Thank your checking and let me know please) **. Please take a look at the second picture:</p>
  
  <p><img src="https://i.stack.imgur.com/VjyqT.png" alt="Faster Fibonacci"></p>
  
  <p>Is my faster fibonacci's algorithm's implementation correct (It seems it is to me because it gets the same values as the first version, but since the first version was too slow I could not compute bigger values with it such as F(75))? What other way can I use to make it faster? Or is there a better way to make it faster? Also <strong>how can I compute Fibonacci for greater values (such as 150, 200) without getting a **long</strong> overflow**? Though it seems fast I would like to push it to the limits. I remember Mr Abrash saying '<strong>The best optimiser is between your two ears</strong>', so I believe it can still be improved. Thank you for helping</p>
  
  <p><strong>[Edition Note:]</strong> Though <a href="https://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time">this</a> question adresses one of the main point in my question, you can see from above that I have additionnal issues.  </p>