#include <stdio.h>                                                                                                              
#include <stdlib.h>                                                                                                             
#include <string.h>                                                                                                             
#include <unistd.h>                                                                                                             
#include <sys/times.h>                                                                                                          
#define TPS sysconf (_SC_CLK_TCK) /* Ticks per sec */                                                                           

static char ** termlist; /* cache for generated fibonacci terms */
static clock_t st_time, en_time; /* start and end timers */       
static struct tms st_cpu, en_cpu;                                 

void start_clock (void); /* start timer */
void end_clock (void); /* end timer and display time elapsed */
void display (FILE *, char *); /* display integer from string */
void * Malloc (size_t); /* wrapper for malloc() */              
char * add (char *, char *); /* add two stringified integers */ 
char * fibogen (int); /* generate nth fibonacci term */         

int main () {
  int n, i;  
  do {       
    printf ("Enter term to calculate: ");
    scanf ("%d", &n);                    
  } while (n<1);                         
  start_clock();                         
  termlist = (char **) Malloc (n*sizeof(char *));
  for (i=0; i<n; i++) {                          
    termlist[i] = (char *) Malloc (sizeof(char));
    termlist[i][0] = '\0';                       
  }                                              
  printf ("fibogen(%d) = ", n);                  
  display (stdout, fibogen (n));                 
  printf ("\n");                                 
  for (i=0; i<n; i++)                            
    free (termlist[i]);                          
  free (termlist);                               
  end_clock();                                   
  return 0;                                      
}                                                

char * fibogen (int n) {
  if (n<3)              
    return "1";         
  /* if fibonacci term is already generated retrieve from array instead of recursion */
  char * temp = add (((strlen(termlist[n-2])) ? termlist[n-2] : fibogen(n-1)),         
                     ((strlen(termlist[n-3])) ? termlist[n-3] : fibogen(n-2)));        
  termlist[n-1] = (char *) Malloc ((strlen(temp)+1)*sizeof(char));                     
  strcpy (termlist[n-1], temp);                                                        
  free (temp);                                                                         
  return termlist[n-1];                                                                
}                                                                                      

void start_clock (void) {
  st_time = times (&st_cpu);
}                           

void end_clock (void) {
  en_time = times (&en_cpu);
  printf ("Real Time: %.2lf, User Time: %.2lf, System Time: %.2lf\n",
          (double)(en_time-st_time)/TPS,
          (double)(en_cpu.tms_utime-st_cpu.tms_utime)/TPS,
          (double)(en_cpu.tms_stime-st_cpu.tms_stime)/TPS);
}

void * Malloc (size_t size) {
  void * p = malloc (size);
  if (!p) perror ("Out of memory!\n");
  return p;
}

void display (FILE * fp, char * num) {
  /* integers are stored with LSB at num[0] */
  char * p = strchr (num, '\0');
  if (p==num)
    putc ('0', fp);
  for (p--; p>=num; p--)
    putc (*p, fp);
}

char * add (char * a, char * b) {
  char *sum, *big, *small, carry = '0';
  size_t i;
  if (strlen(a)>strlen(b)) { big=a; small=b; } else { big=b; small=a; };
  sum = (char *) Malloc ((strlen(big) + 2)*sizeof(char));
  for (i=0; i<strlen(small); i++) {
    sum[i] = (big[i]-'0' + small[i]-'0' + carry-'0') % 10 + '0';
    carry = (big[i]-'0' + small[i]-'0' + carry-'0') / 10 + '0';
  }
  for (; i<strlen(big); i++) {
    sum[i] = (big[i]-'0' + carry-'0') % 10 + '0';
    carry = (big[i]-'0' + carry-'0') / 10 + '0';
  }
  sum[i] = (carry=='0' ? '\0' : carry);
  sum[i+1] = '\0';
  return sum;
}