Fibonacci generator

fib.c

#include <assert.h>
#include <stdio.h>
#include <math.h>

#include "fib.h"

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

/**
 * This function checks if f(n) is in the cache for a given n.
 */
bool
memo_hit (memo cache, int n)
{
  assert (cache != NULL);
  assert (n >= 0);

  /* The array is indexed by n % MEMO_SIZE, so multiple cells will correspond
   * to the same n, and so n needs to be checked.
   */
  return (cache[n % MEMO_SIZE].n == n);
}

/**
 * This function gets f(n) from the cache for a given n. It assumes
 * that f(n) *is* cached.
 */
double
memo_get (memo cache, int n)
{
  /* An assertion will cause the program to die if the condition
   * does not hold.
   * Asserting function preconditions is a good idea to ensure we haven't
   * been given bad data.
   */
  assert (cache != NULL);
  assert (n >= 0);
  assert (memo_hit (cache, n));

  return cache[n % MEMO_SIZE].f;
}

/**
 * This function adds a value to the cache, overwriting whatever
 * was in that cell before.
 */
void
memo_add (memo cache, int n, double f)
{
  assert (cache != NULL);
  assert (n >= 0);

  cache[n % MEMO_SIZE].n = n;
  cache[n % MEMO_SIZE].f = f;
}

/* ***** Fib function ***** */

/**
 * This function calculates fib(n) recursively.
 */
double
fib (int n)
{
  assert (n >= 0);

  /* Static variables retain their value between function calls */
  static memo fibcache;
  double f;

  /* If it's in the cache, just use that value */
  if (memo_hit (fibcache, n))
    return memo_get (fibcache, n);

  /* Calculate */
  f = (n < 2) ? n : fib (n - 1) + fib (n - 2);
  
  /* Add the result to the cache */
  memo_add (fibcache, n, f);

  /* Return the result */
  return f;
}

/* ***** Prompt ***** */

/**
 * This function displays a prompt and receives input
 * until an integer above the minimum value
 */
int
getint (const char* prompt, int min)
{
  assert (prompt != NULL);

  int out;

  do
    {
      printf (prompt);
      scanf  ("%i", &out);
    }
  while (out <= min);

  /* Sometimes it is a good idea to assert a function's
   * postconditions, though this function isn't complex
   * enough to really merit that.
   */
  assert (out > min);

  return out;
}

/* ***** Main function ***** */

int
main (void)
{
  int    limit;
  double phi, error, fib1, fib2;

  /* Get how many Fibonacci numbers to generate */
  limit = getint ("Enter how many fibonacci numbers to generate (> 0): ", 0);

  /* Generate and print all Fibonacci numbers in turn */
  for (int i = 0; i <= limit; i++)
    {
      fib2 = fib1;
      fib1 = fib (i);

      printf ("fib(%i) = %.0f\n", i, fib1);
    }

  /* Using the last two generated, calculate an approximation to phi */
  phi   = fib1 / fib2;
  error = fabs ((100 * (PHI - phi)) / PHI);

  /* Display phi-related output */
  printf ("Approximation of phi = %.0f / %.0f = %f \n", fib1, fib2, phi);
  printf ("True value of phi    = %f\n", PHI);
  printf ("Percentage error     = %f%%\n", error);

 /* Program completed successfully. In main, a nonzero exit code indicates an error. */
 return 0;
}

fib.h

#ifndef __FIB_H
#define __FIB_H

/* For boolean type */
#include <stdbool.h>

/* Magic numbers */
#define MEMO_SIZE 100
#define PHI (double)1.61803398874989484820458683436563811772030917980576

/* Memo type */
typedef struct
{
  int n;
  double f;
} memo[MEMO_SIZE];

/**
 * This function checks if f(n) is in the cache for a given n.
 *
 * @param The cache to check
 * @param The n value to check
 *
 * @return True if there, false otherwise
 */
bool
memo_hit (memo cache, int n);

/**
 * This function gets f(n) from the cache for a given n. It assumes
 * that f(n) *is* cached.
 *
 * @param The cache to check
 * @param The n value to get
 *
 * @return The value of fib(n) for that n
 */
double
memo_get (memo cache, int n);

/**
 * This function adds a value to the cache, overwriting whatever
 * was in that cell before.
 *
 * @param The cache to check
 * @param The n value to add
 * @param The value of fib(n)
 */
void
memo_add (memo cache, int n, double f);

/**
 * This function calculates fib(n) recursively.
 *
 * @param Which Fibonacci number to calculate
 *
 * @return The nth Fibonacci number
 */
double
fib (int n);

/**
 * This function displays a prompt and receives input
 * until an integer above the minimum value
 * is entered.
 *
 * @param The prompt to display
 * @param The minimum value
 *
 * @return The entered integer
 */
int
getint (const char* prompt, int min);

#endif