gistfile1.c

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* ***** Caching stuff ***** */

double *fibcache  = NULL;
int fibcache_size = 0;

bool
fibcache_hit (int n)
{
  return (fibcache_size > n);
}

double
fibcache_get (int n)
{
  return fibcache[n];
}

void
fibcache_add (int n, double f)
{
  if (fibcache_hit (n)) return;
    
  if (fibcache_size <= n)
    {
      fibcache      = realloc (fibcache, (size_t)(n + 1) * sizeof (double));
      fibcache_size = n;
    }

  fibcache[n] = f;
}

/* ***** Fib function ***** */
double
fib (int n)
{
  double f;

  if (fibcache_hit (n))
    f = fibcache_get (n);
  else
    f = (n < 2) ? n : fib (n - 1) + fib (n - 2);
  
  fibcache_add (n, f);

  return f;
}

/* ***** Test ***** */

int
main (void)
{
  for (int i = 0; i < 50; i++)
    printf ("fib(%i) = %.0f\n", i, fib (i));

  return 0;
}