// Department of Computing, Imperial College London
// Operating Systems Concepts 
// Olav Beckmann, with acknowledgements to Paul Kelly
// Tutorial 2 - fibonacci.cc
// 
// Compile this program with gcc -Wall -O2 -o fibonacci fibonacci.c

#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA 100

double time_in_seconds( ) { 
  double result;
  struct timeval tv; 
  struct timezone tz;
  gettimeofday( &tv, &tz );
  result =  (double) tv.tv_sec;
  result += ((double) tv.tv_usec / 1000000.0);
  return result;
}

long fib1( const int n ) {
  if( n == 0 ) {
    return 1;
  }
  if( n == 1 ) {
    return 1;
  }
  else {
    return fib1( n - 1 ) + fib1( n - 2 );
  }
}

long data[MAX_DATA];

long fib2( const int n ) {
  if( n == 0 ) {
    data[n] = 1;
    return data[n];
  }
  if( n == 1 ) {
    data[n] = 1;
    return data[n];
  }
  else {
    data[n] = fib2(n - 1) + fib2(n - 2);
    return data[n];
  }
}

int main( int argc, char *argv[] ) {
  if( argc != 2 ) {
    fprintf( stderr, "Usage: ./fibonacci <n>\n" );
    exit( 1 );
  }
  int n = atoi( argv[1] );

  double time1 = time_in_seconds();
  printf( "Fib1(%d) = %ld.\n", n, fib1( n ) );
  printf( "Fib1 took %f seconds.\n", time_in_seconds() - time1 );
  double time2 = time_in_seconds();
  printf( "Fib2(%d) = %ld.\n", n, fib2( n ) );
  printf( "Fib2 took %f seconds.\n", time_in_seconds() - time2 );

  return 0;
}