Different ways to calculate Fibonacci number - recursive, dynamic, memorize, and multi-threading

Calculating Fibonacci number is an interesting computer  science problem.

fib (n) = fib (n-1) + fib(n-2).

There are many ways to implement the Fibonacci calculator. Following are Java implementations.


1. Recursion. Looks pretty, just like math formula. Lots of stack frames get created. Expensive to run. Hard to mix with multi-threading

 /**
  * calculate Fibonacci number through Recursion.
  * 
  * Recursion. Looks pretty, just like math formula. Lots of stack frames get created. Expensive to run.
  *   
  * @param number
  * @return
  */
    static long getFibViaRecursion(long number) {
     if (number==0 || number==1)
      return number;
     else 
      return getFibViaRecursion(number-1) + getFibViaRecursion(number-2);
    }

    static void testFibViaRecursion () {
  long start = System.currentTimeMillis();
     System.out.println("getFibViaRecursion(10) - " + getFibViaRecursion(10) );
     System.out.println("getFibViaRecursion(20) - " + getFibViaRecursion(20) );
     System.out.println("getFibViaRecursion(40) - " + getFibViaRecursion(40) );
  long end = System.currentTimeMillis() - start;
  System.out.println("FibViaRecursion took: " + end + "ms");
    }

2. Straight Dynamic. Short in this case, easy to follow, fast.

 /**
  * calculate Fibonacci number with straight forward dynamic method. 
  * 
  * Straight Dynamic. Short in this case, easy to follow, fast.  
  * 
  * @author lei zou
  *
  */
    static long getFibViaDynamic(long number) {
     long val1 = 0;
     long val2 = 1;
     long sum = val1 + val2;
     for (long i=1; i<number; i++) {
      sum = val1 + val2;
      val1 = val2;
      val2 = sum;
     }
     return sum;
    }

    static void testFibViaDynamic () {
  long start = System.currentTimeMillis();
     System.out.println("getFibViaDynamic(10) - " + getFibViaDynamic(10) );
     System.out.println("getFibViaDynamic(20) - " + getFibViaDynamic(20) );
     System.out.println("getFibViaDynamic(50) - " + getFibViaDynamic(50) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testFibViaDynamic took: " + end + "ms");
    }

3. Dynamic memorize with Hashtable - cool, less calculation, higher memory requirement.

    
    static void testDynamicFibViaHashTable () {
  long start = System.currentTimeMillis();
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(10) ) - " + new DynamicFibViaHashTable().getFib( new Long(10) ) );
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(20) ) - " + new DynamicFibViaHashTable().getFib( new Long(20) ) );
     System.out.println("new DynamicFibViaHashTable().getFib( new Long(50) ) - " + new DynamicFibViaHashTable().getFib( new Long(50) ) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testDynamicFibViaHashTable took: " + end + "ms");
    }

    /**
     * 
     * calculate Fibonacci number through memorize (Hashtable)
     * 
     * Dynamic memorize with Hashtable, cool, less calculation, higher memory requirement.     
     * 
     * @author lei zou
     *
     */
 static public class DynamicFibViaHashTable {
  private Hashtable<Long,Long> memorize = new Hashtable<Long,Long>() {
   {
    put(new Long(0),new Long(0));
    put(new Long(1),new Long(1));
   }
  };

     Long getFib(Long number) {

         if (memorize.containsKey(number))  return memorize.get(number); // Return it.
         
         Long val1 = (memorize.containsKey(number-1)) ? memorize.get(number-1) : getFib( number-1);
         Long val2 = (memorize.containsKey(number-2)) ? memorize.get(number-2) : getFib( number-2);

         // The number hasn't been calculated, so let's calculate it.
         Long val = val1+val2;

         // Store the value for later use.
         memorize.put(number, val);
         return val;
     }
 }

4. Dynamic memorize with HashMap - cool, less calculation, higher memory requirement, faster than Hashtable. This is because that Hashtable is synchronized.

 /**
  * calculate Fibonacci number through memorize (HashMap)
  * 
  */
 static void testDynamicFibViaHashMap () {
  long start = System.currentTimeMillis();
     System.out.println("new DynamicFibViaHashMap().getFib( 10 ) - " + new DynamicFibViaHashMap().getFib( 10 ) );
     System.out.println("new DynamicFibViaHashMap().getFib( 20 ) - " + new DynamicFibViaHashMap().getFib( 20 ) );
     System.out.println("new DynamicFibViaHashMap().getFib( 50 ) - " + new DynamicFibViaHashMap().getFib( 50 ) );
  long end = System.currentTimeMillis() - start;
  System.out.println("testDynamicFibViaHashMap took: " + end + "ms");
    }
 
 static public class DynamicFibViaHashMap {

  private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

  public DynamicFibViaHashMap() {
    memoize.put(0, BigInteger.ZERO);
    memoize.put(1, BigInteger.ONE);
  }

  public BigInteger getFib(final int index) {

   if (!memoize.containsKey(index)) {
    BigInteger val1 = memoize.containsKey(index-1) ? memoize.get(index-1) : getFib(index - 1);
    BigInteger val2 = memoize.containsKey(index-2) ? memoize.get(index-2) : getFib(index - 2);
    memoize.put(index, val1.add(val2));
   }

     return memoize.get(index);
    }
 }

5. Dynamic memorize with ConcurrentHashMap in multi-threaded - less calculation, not necessary to speed up the calculation because thread creation is expensive.

 static void testMultiThreadDynamicFib () {
  long start = System.currentTimeMillis();
  MultiThreadDynamicFib proc = new MultiThreadDynamicFib();
     System.out.println("proc.getFib( 10 ) - " + proc.getFib( 10 ) );
     System.out.println("proc.getFib( 20 ) - " + proc.getFib( 20 ) );
     System.out.println("proc.getFib( 50 ) - " + proc.getFib( 50 ) );
     proc.shutDown();
  long end = System.currentTimeMillis() - start;
  System.out.println("testMultiThreadDynamicFib took: " + end + "ms");
    }

 /**
  * calculate Fibonacci number through memorize (ConcurrentHashMap) with multi-threads
  * 
  * @author lei zou
  *
  */
 static public class MultiThreadDynamicFib  {

  private final ExecutorService threads = Executors.newCachedThreadPool();
  
  private ConcurrentHashMap<Integer, BigInteger> memorize = new ConcurrentHashMap<Integer, BigInteger>();

  public void shutDown () {
   threads.shutdown();
  }
  private Callable<BigInteger> createTask (final int index) {
   return new Callable<BigInteger>() {
    @Override
    public BigInteger call() throws Exception {
     return splitFibNumberAtIndex(index);
    }
   };
  }

  public BigInteger getFib(final int index) {
   if (memorize.containsKey(index)) return memorize.get(index);
   
      FutureTask<BigInteger> task = new FutureTask<BigInteger>(createTask(index));
      threads.submit(task);
      BigInteger val =  null;
   while ( val==null && ! task.isDone() ) {
       try {
        val = task.get();
    } catch (InterruptedException e) {
     e.printStackTrace();
    } catch (ExecutionException e) {
     e.printStackTrace();
    } 
      }

   if (val!=null) {
    memorize.putIfAbsent(index, val);
   }
      return val;
     }
  
  public MultiThreadDynamicFib() {
   memorize.put(0, BigInteger.ZERO);
   memorize.put(1, BigInteger.ONE);
  }

  
  public BigInteger splitFibNumberAtIndex(final int index) {

   if (!memorize.containsKey(index)) {
    BigInteger val1 = memorize.containsKey(index-1) ?memorize.get(index-1) :  getFib(index - 1);
    BigInteger val2 = memorize.containsKey(index-2) ?memorize.get(index-2) :  getFib(index - 2);
    memorize.putIfAbsent(index, val1.add(val2));
   }
     return memorize.get(index);
    }
 }
 

Here is the main method:

    public static void main(String [] args) {

     testFibViaDynamic ();
     testFibViaRecursion ();
     testDynamicFibViaHashTable() ;
        testDynamicFibViaHashMap ();     
        testMultiThreadDynamicFib ();
    }

getFibViaDynamic(10) - 55
getFibViaDynamic(20) - 6765
getFibViaDynamic(50) - 12586269025
testFibViaDynamic took: 1ms

getFibViaRecursion(10) - 55
getFibViaRecursion(20) - 6765
getFibViaRecursion(40) - 102334155
FibViaRecursion took: 1086ms

new DynamicFibViaHashTable().getFib( new Long(10) ) - 55
new DynamicFibViaHashTable().getFib( new Long(20) ) - 6765
new DynamicFibViaHashTable().getFib( new Long(50) ) - 12586269025
testDynamicFibViaHashTable took: 6ms

new DynamicFibViaHashMap().getFib( 10 ) - 55
new DynamicFibViaHashMap().getFib( 20 ) - 6765
new DynamicFibViaHashMap().getFib( 50 ) - 12586269025
testDynamicFibViaHashMap took: 3ms

proc.getFib( 10 ) - 55
proc.getFib( 20 ) - 6765
proc.getFib( 50 ) - 12586269025
testMultiThreadDynamicFib took: 71ms

Enjoy the journey.