Fibonacci Generator 2004

A fairly acute Fibonacci sequence generator written in the C programming language. I wrote this in the summer of 2004 (although I've updated it since then) to get me ready for third University in which I was told I would require to know C, which I had never used before. So within two weeks of starting to learn C I had written this program (which was really just a conversion of the Ada version I had done in second year).

The Fibonacci algorithm was invented by an Italian mathematician (Fibonacci) to predict rabbit growth. A lot of assumptions are made, some of which are a bit sillier than others:

Assume that you start with two rabbits.
Assume that once a rabbit is three years old, it is capable of mating.
Assume that all rabbits capable of mating will in fact mate.
Assume that every time two rabbits mate, one offspring is produced without failure; no more, no less.
Assume rabbits can only produce one 'litter' a year.
Assume that there is an almost equal number of male and female rabbits.
Assume rabbits never die.

Anyway, the interesting thing about the Fibonacci algorithm is that it can be implemented recursively, and the numbers get big VERY quickly. The most basic way of expressing the algorithm is shown below:

fib[n] = fib[n-1] + fib[n-2]

where fib[1] = 1, fib[2] = 1

You can download all the source code of the program here or view it below.

fib.c:

/*--------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     Program Title : Fast-Fib Version 0.9                               --
--     Author : nex                                                       --
--     Date Last Modified : 15th December 2004                            --
--                                                                        --
--     Description : This program takes in two integers from standard     --
--                   input and uses them as indices to calculate          --
--                   Fibonacci numbers from the lower to upper index.     --
--                                                                        --
--                   This program uses a large integer representation     --
--                   for large integer values produced by the Fibonacci   --
--                   algorithm (to prevent overflow).                     --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
#include <stdio.h>
 
 
 
/**************************************************************************/
/* Representation for big integers (a linked list) */
 
  struct big_list {
    int Val;
    struct big_list *Next;
    struct big_list *Prev;
  };
  struct big {
    struct big_list *Head;
    struct big_list *Tail;
  };
 
/**************************************************************************/
 
 
 
/**************************************************************************/
/*---- Function defintions -----------------------------------------------*/
 
  /* Definitions for the fast Fibonacci algorithm functions */
    struct big helpFib(int n, int k, struct big fibk, struct big fibk1);
    struct big Fib(int n);
    int Verify(int n);
 
  /* Definitions for the use of the representation of big integers */
    struct big Add(struct big x, struct big y);
    int IsEqual(struct big x, struct big y);
    struct big MakeLittleBig(int val);
    void WriteBig(struct big x);
    struct big_list *lalloc(void);
 
/**************************************************************************/
 
 
 
 
 
 
/**************************************************************************/
/**************************************************************************/
main()
  {  
 
    int LowFib, HiFib, Swap, i;
 
    /* Get Lower and Upper values to run algorithm from and to */
    printf("\nEnter low number: ");
    scanf("%d", &LowFib);
    printf("Enter high number: ");
    scanf("%d", &HiFib);
    printf("\n");
 
    /* Check that Lower and Upper values are positive */
    if ((LowFib < 1) || (HiFib < 1)) {
      printf("\nFibonacci Indices must be positive integers greater than"); 
      printf(" zero.");
    }
    else {
      /* Check that Lower Limit is less than the Upper Limit and swap if */
      /* appropriate */
      if (LowFib > HiFib) {
	Swap = LowFib;
	LowFib = HiFib;
	HiFib = Swap;
      }
 
      /* Find, validate and output requested Fibonacci sequence */
      for ( i = LowFib; i <= HiFib; i++) {
	printf("Fib(%d) = ", i);
	WriteBig(Fib(i));
	if (Verify(i))
	  printf("    Valid\n");
	else
	  printf("    Invalid\n");
      }
    }
 
    /* Prevent unwanted output messages at end of program */
    return 0;
  }
 
/**************************************************************************/
/**************************************************************************/
 
 
 
 
 
 
/**************************************************************************/
/*---- Fibonacci specific functions --------------------------------------*/
 
  /************************************************************************/
  /* helpFib is used to speed up the Fib function by preventing repeated 
     calculations. In truth, I only ever briefly understood how this works. 
     I didn't come up with it and I understood it just long enough to 
     program it in the original Ada version of this program. */
 
  struct big helpFib(int n, int k, struct big fibk, struct big fibk1)
    {
      if (n == k)
        return fibk;
      else
        return (helpFib(n,(k + 1), Add(fibk, fibk1), fibk));
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* The Fib function calculates the value of the Fibonacci number with 
     index n. */
 
  struct big Fib(int n)
    {
      struct big Big_One, Big_Zero;
 
      Big_One = MakeLittleBig(1);
      Big_Zero = MakeLittleBig(0);
 
      /* For values less than 3, the Fib number is 1 */
      if (n < 3)
        return Big_One;
 
      /* For Fibonacci indices smaller than 21, use a simple recursive Fib 
         function as this produces the most optimal peformance */
      else if (n < 21)
        return (Add((Fib(n-2)), (Fib(n-1))));
 
      /* For indices larger than 20, use the helpFib function to
         speed things up. */
      else
        return (helpFib(n, 1, Big_One, Big_Zero));
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* The Verify procedure tests to see if the Fibonacci number
     calculated is accurate by trying to find it by a different 
     algorithm (which, incidentally, uses the same algorithm as the 'main
     program' as it were) and then comparing it to the originally found 
     value. */
 
  int Verify(int n)
    {
      struct big test;
 
      if (n != 2) {
         test = Fib(n);
 
         /* The 'Add' function is required to add numbers represented using
         the 'big' structure */
         test = Add(Add(test,test),test);
 
         /* The 'IsEqual' function is required to compare numbers represented 
         using the 'big' structure */
         if (IsEqual(test, Add(Fib(n+2), Fib(n-2))))
           return 1;
         else
           return 0;
      }
      else
        return 1;
    }
 
/**************************************************************************/
 
/*---- End of Fibonacci specific functions -------------------------------*/
/**************************************************************************/
 
 
 
 
 
/**************************************************************************/
/*---- Big integer specific functions ------------------------------------*/
 
  /************************************************************************/
  /* Make a new 'big' integer type with value 'val' (which must be less 
     than 1000 */
 
  struct big MakeLittleBig(int val)
    {
      struct big_list *One_L;
      struct big One;
 
      One_L = NULL;
      One_L = lalloc();
      One_L->Val = val;
      One_L->Next = One_L->Prev = NULL;
      One.Head = One.Tail = One_L;
      return One;
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* Outputs the value of the 'big' type 'x' to standard output. */
 
  void WriteBig(struct big x)
    {
      struct big X_Temp;
 
      X_Temp = x;
      if (x.Tail != NULL) {
 
	/* Extra zeros will need to be printed if current node value is less
           than 100 */
        if (x.Tail->Next != NULL) {
          if (x.Tail->Val < 100) {
	    if (x.Tail->Val < 10)
	      printf("00");
            else
	      printf("0");
          }
        }
	/* Output current node value then recursively call other node 
           values for output. */
        printf("%d", (x.Tail->Val));
        X_Temp.Tail = x.Tail->Prev;
        WriteBig(X_Temp); 
      }
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* Returns the boolean expression x=y */
 
  int IsEqual(struct big x, struct big y)
    {
      struct big X_Temp, Y_Temp;
 
      X_Temp = x;
      Y_Temp = y;
 
      /* Test all possible cases in which x == y (or x != y),
         using recursion to call all nodes. */
      if((X_Temp.Head != NULL) && (Y_Temp.Head != NULL)) {
        if (X_Temp.Head->Val == Y_Temp.Head->Val) {
          X_Temp.Head = X_Temp.Head->Next;
          Y_Temp.Head = Y_Temp.Head->Next;
          return (IsEqual(X_Temp, Y_Temp));
        } 
        else
          return 0;
      }
      else if ((X_Temp.Head != NULL) && (Y_Temp.Head == NULL))
        return 0;
      else if ((X_Temp.Head == NULL) && (Y_Temp.Head != NULL))
        return 0;
      else if ((X_Temp.Head == NULL) && (Y_Temp.Head == NULL))
        return 1;
      else
        return 0;
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* Calculates x + y (both of type 'big') and returns as type 'big'. This 
     function is specifically designed for the big type. */
 
  struct big Add(struct big x, struct big y)
    {
      /* Clear variables of data */
      struct big X_Temp, Y_Temp, R, R_Temp;
      int C, S, P, Q;
 
      C = S = P = Q = 0;
      R_Temp.Head = R_Temp.Tail = R.Head = R.Tail = NULL;
 
      X_Temp = x;
      Y_Temp = y;
 
      /* If x or y have no values, return R (which will == null) */
      if ((x.Head != NULL) || (y.Head != NULL)) {
 
	/* If there is still data in the current X_Temp or Y_Temp or there
           is a carry, get intermediate values for use in equations */
        while((X_Temp.Head != NULL) || (Y_Temp.Head != NULL) || (C == 1)) {
          if ((X_Temp.Head == NULL) && (Y_Temp.Head != NULL)) {
	    Q = Y_Temp.Head->Val;
	    Y_Temp.Head = Y_Temp.Head->Next;
	    P = 0;
          }
          else if ((X_Temp.Head != NULL) && (Y_Temp.Head == NULL)) {
	    P = X_Temp.Head->Val;
            X_Temp.Head = X_Temp.Head->Next;
            Q = 0;
          }
          else if ((X_Temp.Head == NULL) && (Y_Temp.Head == NULL)) {
            P = Q = 0;
          }
          else {
            P = X_Temp.Head->Val;
            X_Temp.Head = X_Temp.Head->Next;
            Q = Y_Temp.Head->Val;
            Y_Temp.Head = Y_Temp.Head->Next;
          }
 
	  /* Use intermediate values to calculate sum and carry */
          if (R.Head == NULL) {
	    S = ((P + Q) % 1000);
	    C = ((P + Q) / 1000);
          }
          else {
	    S = ((P + Q + C) % 1000);
	    C = ((P + Q + C) / 1000);
          }
 
	  /* Add new nodes containing correct values to doubly linked 
             list */
          if (R.Head == NULL) {
	    R.Head = lalloc();
	    R.Head->Val = S;
	    R.Head->Next = R.Head->Prev = NULL;
	    R.Tail = R.Head;
          }
          else {
	    R.Tail->Next = lalloc();
	    R.Tail->Next->Val = S;
	    R.Tail->Next->Next = R.Tail->Next->Prev = NULL;
	    R_Temp = R;
	    R.Tail = R.Tail->Next;
	    R.Tail->Prev = R_Temp.Tail;
          }
        }
      }
      return R;
    }
 
  /************************************************************************/
 
 
 
  /************************************************************************/
  /* This is required to create new 'nodes' in the linked list (i.e. it
     allocates space in memory for next node) */
 
  struct big_list *lalloc(void)
    {
      return (struct big_list *) malloc(sizeof(struct big_list));
    }
 
  /************************************************************************/
 
/*---- End of Big integer specific functions -----------------------------*/
/**************************************************************************/
 
 
 
 
 
/*---- End of Fast-Fib program -------------------------------------------*/
/**************************************************************************/

To use the program enter the low number you want the Fibonacci sequence to start from then the high number you want it to finish with.

Input (each end of line is an 'enter'):

4
600

Output:

Fib(n) = fibnumber Valid OR Invalid
Fib(n + 1) = next_fibnumber Valid OR Invalid

None, but for large Fibonacci indices, the computer may crash from running out of memory.

— Nexami Engeo 2007/07/05 17:18