effin around with ibonacci

First off, thanks to Alex Gorbatchev for his awesome SyntaxHighlighter. I've used it here with his great instructions for embedding. I took his instructions here using the "pre" method and just embedded the scripts within the script tags of this post instead of referencing them. If I use this again, I'll figure out how to upload the scripts I need to blogger, so I can just reference them. Anyway... this is really high quality stuff, nice work Alex.

So, I was playing around with, or did I say effin around with ibonacci? (Yes, putting the "f" in fibonacci.) I wanted to try out a few variations of Fibonacci algos to do some speed comparisons. I was knew that recursion would take a bit of a hit, but I was really surprised that it would be this bad.

recurFib(45) took 6813 milliseconds to calculate 1134903170
iterFib(45) took 0 milliseconds to calculate 1134903170
iterNoArrFib(45) took 0 milliseconds to calculate 1134903170

I love the elegance of recursive code.

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

As opposed to the faster-performing iterative code.

public static int iterNoArrFib(int n) {
  int f = 0;
  //special case #1
  if (n == 0) {
   return f;
  }
  
  int x = 1;
  int y = 1;
  //special case #2
  if (n <=2) {
   return x;
  }
  
  for (int i = 3; i <= n; i++ ) {
   f = x + y;
   //set up x and y for next loop
   y = x;
   x = f;
   
  }
  return f;
 }

So, I tried a couple of things. First, I tried to neaten up the iterative version with an array instead of shuffling through the variables:

public static int iterFib(int n) {
  int[] f = new int[n+1];
  f[0] = 0;
  f[1] = 1;
  if (n >= 2) {
   f[2] = 1;
  }
  for (int i = 3; i <= n; i++ ) {
   f[i] = f[i - 1] + f[i - 2];
   
  }
  return f[n];
 }

It was no faster or slower (by my crude benchmark), but a little cleaner. Then, I tried to speed up our recursive version with a little caching. I was pretty sure that the recursive version recalculates all of the children for each node of the tree, so, I added an array to cache values, checking to see if it was already calculated before doing a recursive call:

private static int[] recurCache ;
 
 public static int recurCacheFib(int n, boolean first) {
  
  recurCache = (recurCache == null || first)? new int[n+1] : recurCache ;
  
  if (n == 0) {
   recurCache[n] = 0;
   return n;
  }
  if (n <= 2) {
   recurCache[n] = 1;
   return 1;
  }
  
  int f = recurCache[n];
  if (f == 0) {
   f = recurCacheFib(n - 1,false) + recurCacheFib(n - 2,false);
   recurCache[n] = f;
  }
  
  return f;
 }

Well, low and behold, it was just as fast as the iterative version:

recurFib(45) took 6813 milliseconds to calculate 1134903170
recurCacheFib(45) took 0 milliseconds to calculate 1134903170
recurCacheFib(45) took 0 milliseconds to calculate 1134903170 a second time
iterFib(45) took 0 milliseconds to calculate 1134903170
iterNoArrFib(45) took 0 milliseconds to calculate 1134903170

I ran it twice just to see if I would take much of a hit recreating the array for the cache. Apparently not.

However, when I compare the cached recursion code to the array-based version of iterative code, I think the array-based version is slightly more elegant. This is mostly due to the addition of the external array and not just lines of code. What do you think? The entire code is below.

package org.bikeonastick.examples;

import java.util.ArrayList;
import java.util.List;

public class Fibonacci {
 
 public static void main(String[] args) {
  int toFib = Integer.parseInt(args[0]);
  long start = System.currentTimeMillis();
  int fib = Fibonacci.recurFib(toFib);
  long finish = System.currentTimeMillis();
  System.out.println("recurFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
  start = System.currentTimeMillis();
  fib = Fibonacci.recurCacheFib(toFib,true);
  finish = System.currentTimeMillis();
  System.out.println("recurCacheFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);

  start = System.currentTimeMillis();
  fib = Fibonacci.recurCacheFib(toFib,true);
  finish = System.currentTimeMillis();
  System.out.println("recurCacheFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib + " a second time");

  
  start = System.currentTimeMillis();
  fib = Fibonacci.iterFib(toFib);
  finish = System.currentTimeMillis();
  System.out.println("iterFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
  start = System.currentTimeMillis();
  fib = Fibonacci.iterNoArrFib(toFib);
  finish = System.currentTimeMillis();
  System.out.println("iterNoArrFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
 }
 
 public static int recurFib(int n) {
  if (n == 0) {
   return n;
  }
  if (n <= 2) {
   return 1;
  }
  return recurFib(n - 1) + recurFib(n - 2);
 }
 
 private static int[] recurCache ;
 
 public static int recurCacheFib(int n, boolean first) {
  
  recurCache = (recurCache == null || first)? new int[n+1] : recurCache ;
  
  if (n == 0) {
   recurCache[n] = 0;
   return n;
  }
  if (n <= 2) {
   recurCache[n] = 1;
   return 1;
  }
  
  int f = recurCache[n];
  if (f == 0) {
   f = recurCacheFib(n - 1,false) + recurCacheFib(n - 2,false);
   recurCache[n] = f;
  }
  
  return f;
 }

 
 public static int iterFib(int n) {
  int[] f = new int[n+1];
  f[0] = 0;
  f[1] = 1;
  if (n >= 2) {
   f[2] = 1;
  }
  for (int i = 3; i <= n; i++ ) {
   f[i] = f[i - 1] + f[i - 2];
   
  }
  return f[n];
 }
 
 public static int iterNoArrFib(int n) {
  int f = 0;
  //special case #1
  if (n == 0) {
   return f;
  }
  
  int x = 1;
  int y = 1;
  //special case #2
  if (n <=2) {
   return x;
  }
  
  for (int i = 3; i <= n; i++ ) {
   f = x + y;
   //set up x and y for next loop
   y = x;
   x = f;
   
  }
  return f;
 }

}