/*------------------------------------------------------------------------------
 * fib.c: fibonacci
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <sys/time.h>

/*------------------------------------------------------------------------------
 * Constants
**----------------------------------------------------------------------------*/

#define NMAX_FIB    40

/*------------------------------------------------------------------------------
 * Global Variables
**----------------------------------------------------------------------------*/

static int FT[NMAX_FIB] = {0, 1};

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static int fib(int n) 
{
    if (n == 0) return (0);
    if (n == 1) return (1);
    return (fib(n - 1) + fib(n - 2));
}

/*----------------------------------------------------------------------------*/

static int fib_dp(int n)
{
    int i;

    if (!FT[n])
	for (i = 2; i <= n; i++)
	    if (!FT[i]) FT[i] = FT[i - 1] + FT[i - 2];

    return (FT[n]);
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    int i;
    double time_diff1, time_diff2;
    struct timeval st, et;

    gettimeofday(&st, NULL);
    for (i = 0; i < NMAX_FIB; i++)
	printf("%d. %d\n", i, fib(i));
    gettimeofday(&et, NULL);
    time_diff1 = (double)((et.tv_sec - st.tv_sec) + (et.tv_usec - st.tv_usec)/1000000.0);

    gettimeofday(&st, NULL);
    for (i = 0; i < NMAX_FIB; i++)
	printf("%d. %d\n", i, fib_dp(i));
    gettimeofday(&et, NULL);
    time_diff2 = (double)((et.tv_sec - st.tv_sec) + (et.tv_usec - st.tv_usec)/1000000.0);

    printf("%0.4lf vs. %0.4lf seconds\n", time_diff1, time_diff2);

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=c
**----------------------------------------------------------------------------*/