Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_blog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/blog/action.php on line 154

Strict Standards: Declaration of action_plugin_include::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/include/action.php on line 140

Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldindex/action.php on line 57

Strict Standards: Declaration of action_plugin_discussion::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/discussion/action.php on line 955

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 205

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 208

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 389

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 530

Strict Standards: Declaration of cache_instructions::retrieveCache() should be compatible with cache::retrieveCache($clean = true) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/cache.php on line 291

Deprecated: Function split() is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/auth.php on line 154

Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 71
nex code:c:fibonacci
 
Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/parser.php on line 66

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/lexer.php on line 292

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 22

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 49

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 213

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 241

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 295

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 328

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/handler.php on line 575

Deprecated: Function split() is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/lexer.php on line 510

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 939

Strict Standards: call_user_func() expects parameter 1 to be a valid callback, non-static method Doku_Renderer_xhtml::_tocitem() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/html.php on line 741

Strict Standards: Non-static method Doku_Renderer_xhtml::_xmlEntities() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 119

Strict Standards: call_user_func() expects parameter 1 to be a valid callback, non-static method Doku_Renderer_xhtml::_tocitem() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/html.php on line 741

Strict Standards: Non-static method Doku_Renderer_xhtml::_xmlEntities() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 119

Strict Standards: call_user_func() expects parameter 1 to be a valid callback, non-static method Doku_Renderer_xhtml::_tocitem() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/html.php on line 741

Strict Standards: Non-static method Doku_Renderer_xhtml::_xmlEntities() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 119

Strict Standards: call_user_func() expects parameter 1 to be a valid callback, non-static method Doku_Renderer_xhtml::_tocitem() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/html.php on line 741

Strict Standards: Non-static method Doku_Renderer_xhtml::_xmlEntities() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 119

Strict Standards: call_user_func() expects parameter 1 to be a valid callback, non-static method Doku_Renderer_xhtml::_tocitem() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/html.php on line 741

Strict Standards: Non-static method Doku_Renderer_xhtml::_xmlEntities() should not be called statically in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parser/xhtml.php on line 119

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).

Description

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

The Source Code

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 -------------------------------------------*/
/**************************************************************************/

Example of Use

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

Assumptions

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

Nexami Engeo 2007/07/05 17:18


Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 79