Three different fibonacci variants with simple performance tests and Stackframe analysis

fibonacci.pde

//Autor: Christopher Schölzel

// -------------------------------------------
// -- Musterlösungen zu Fibonacci-Varianten --
// -------------------------------------------

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

int fibIter(int n) {
  if (n <= 1) return n;
  int secondlast = 0;
  int last = 1;
  int current = 0;
  for(int i = 2; i <= n; i++) {
    current = last + secondlast;
    secondlast = last;
    last = current;
  }
  return current;
}

int fibCache(int n) {
  return fibCache(n, new int[n+1]);
}
int fibCache(int n, int[] cache) {
  if (n <= 1) return n;
  if (cache[n] > 0) return cache[n];
  cache[n] = fibCache(n-2,cache)+fibCache(n-1,cache);
  return cache[n];
}
// ----------------------------------------------------------------------
// -- Modifizierte fibonacci-Versionen mit Buchhaltung der Stackframes --
// ----------------------------------------------------------------------

int fibCalls = 0;
int fibFrames = 0;
int fibFramesMax = 0;
int fibLog(int n) {
  int res;
  fibCalls++;
  fibFrames++; //Stackframe geöffnet bei Aufruf
  if(fibFrames > fibFramesMax) fibFramesMax = fibFrames;
  res = n <= 1 ? n : fibLog(n-2)+fibLog(n-1);
  fibFrames--; //Stackframe wird geschlossen mit return
  return res;
}

int fibIterCalls = 0;
int fibIterFrames = 0;
int fibIterFramesMax = 0;
int fibIterLog(int n) {
  fibIterCalls++;
  fibIterFrames++; //müßig, aber es geht ums Prinzip
  if(fibIterFrames > fibIterFramesMax) fibIterFramesMax = fibIterFrames;
  int res;
  if (n <= 1) res = n;
  else {
    int secondlast = 0;
    int last = 1;
    int current = 0;
    for(int i = 2; i <= n; i++) {
      current = last + secondlast;
      secondlast = last;
      last = current;
    }
    res = current;
  }
  fibIterFrames--;
  return res;
}

int fibCacheCalls = 0;
int fibCacheFrames = 0;
int fibCacheFramesMax = 0;
int fibCacheLog(int n) {
  return fibCacheLog(n,new int[n+1]);
}
int fibCacheLog(int n, int[] cache) {
  fibCacheCalls++;
  fibCacheFrames++;
  if(fibCacheFrames > fibCacheFramesMax) fibCacheFramesMax = fibCacheFrames;
  int res;
  if (n <= 1) res = n;
  else if (cache[n] > 0) res = cache[n];
  else {
    cache[n] = fibCacheLog(n-1,cache)+fibCacheLog(n-2,cache);
    res = cache[n];
  }
  fibCacheFrames--;
  return res;
}

int param = 30;
float fibTime,fibIterTime,fibCacheTime;
void setup() {
  size(400,400);
  noLoop();
  //Zum Vergleich alle Log-Varianten mit gleichem Parameter aufrufen
  println("fibIterLog("+param+") =",fibIterLog(param),"=",fibIter(param));
  println("fibCacheLog("+param+") =",fibCacheLog(param),"=",fibCache(param));
  println("fibLog("+param+") =",fibLog(param),"=",fib(param));
  
  //Zur Zeitmessung werden die Ausführungen 100 mal wiederholt
  int n = 100;
  fibTime = millis();
  for(int i = 0; i < n; i++) fib(param);
  fibTime = millis()-fibTime;
  fibTime /= n;
  println("fibTime =",fibTime);
  //bzw öfter für die schnelleren Varianten, um überhaupt etwas zu messen
  n = 1000000; //Eine Million Durchläufe
  fibCacheTime = millis();
  for(int i = 0; i < n; i++) fibCache(param);
  fibCacheTime = millis()-fibCacheTime;
  fibCacheTime /= n;
  println("fibCacheTime =",fibCacheTime);
  
  n = 100000000; //100 Millionen Durchläufe
  fibIterTime = millis();
  for(int i = 0; i < n; i++) fibIter(param);
  fibIterTime = millis()-fibIterTime;
  fibIterTime /= n;
  println("fibIterTime =",fibIterTime);
}

void draw() {
  background(255);
  float ydist = 120;
  drawStatistics("fib("+param+")",fibTime,fibCalls,fibFramesMax);
  translate(0,ydist);
  drawStatistics("fibIter("+param+")",fibIterTime,fibIterCalls,fibIterFramesMax);
  translate(0,ydist);
  drawStatistics("fibCache("+param+")",fibCacheTime,fibCacheCalls,fibCacheFramesMax);
}

void drawStatistics(String name, float time, int calls, int maxFrames) {
  textAlign(LEFT);
  textSize(16);
  fill(0);
  String s = name;
  s += "\nZeit in Nanosekunden: "+nf(time*1000,1,6);
  s += "\nAufrufe der Funktion: "+calls;
  s += "\nMaximale Stacktiefe : "+maxFrames;
  text(s,5,20);
}