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_2
 

Fibonacci Generator 2005

A fairly acute Fibonacci sequence generator written in the C programming language. This is a conversion of my earlier Fibonacci Generator 2004 which was just one file. This version was split up to include a header file so that all the BigInt representation stuff is kept seperate from the main Fibonacci code. But in essence, there is really no difference between the programs, just the way in which the source code is laid out. This also makes it easier for anyone else to use my BigInt library in their own programs should they wish to (or improve it if they get the inspiration).

In essence I've really just come full circle - this is now my fifth version of the Fast-Fib program, and until this version, the first one was the only one that had the BigInt stuff seperate from the main program.

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 2.4                               --
--     Author : nex                                                       --
--     Date Last Modified : 1st January 2005                              --
--                                                                        --
--     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) contained in         --
--                   bigint.h.                                            --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
#include <stdio.h>
#include "bigint.h"
 
 
 
 
/**************************************************************************/
/*---- 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);
 
/**************************************************************************/
 
 
 
 
 
 
/**************************************************************************/
/**************************************************************************/
int main(void)
  {  
 
    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 -------------------------------*/
/**************************************************************************/
 
 
/*---- End of Fast-Fib program -------------------------------------------*/
/**************************************************************************/

bigint.h:

/*--------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     Program Title : BigInt Version 0.4                                 --
--     Author : nex                                                       --
--     Date Last Modified : 1st January 2005                              --
--                                                                        --
--     Description : This program is for the handling of large integers   --
--                   by using a linked list representation. The intended  --
--                   purpose is to provent overflow when wanting to deal  --
--                   with very large integers.                            --
--                                                                        --
--     State of Program: The program is still being tested and has only   --
--                       the functions I have thus far required. It does  --
--                       not contain all the functions one might expect   --
--                       from such a package.                             --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
#ifndef H_BIGINT
#define H_BIGINT
 
/**************************************************************************/
/* 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 use of the representation of big integers */
 
 
    /************************************************************************/
    /* Make a new 'big' integer type with value 'val' (which must be less 
       than 1000 */
    struct big MakeLittleBig(int);
 
 
    /************************************************************************/
    /* Outputs the value of the 'big' type 'x' to standard output. */
    void WriteBig(struct big);
 
 
    /************************************************************************/
    /* Returns the boolean expression x=y */
    int IsEqual(struct big, struct big);
 
 
    /************************************************************************/
    /* 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, struct big);
 
 
    /************************************************************************/
    /* 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);
 
 
/**************************************************************************/
 
#endif

bigint.c:

/*--------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     Program Title : BigInt Version 0.4                                 --
--     Author : nex                                                       --
--     Date Last Modified : 1st January 2005                              --
--                                                                        --
--     Description : This program is for the handling of large integers   --
--                   by using a linked list representation. The intended  --
--                   purpose is to provent overflow when wanting to deal  --
--                   with very large integers.                            --
--                                                                        --
--     State of Program: The program is still being tested and has only   --
--                       the functions I have thus far required. It does  --
--                       not contain all the functions one might expect   --
--                       from such a package.                             --
--                                                                        --
----------------------------------------------------------------------------
--------------------------------------------------------------------------*/
 
#include <stdio.h>
#include <stdlib.h>
#include "bigint.h"
 
 
/**************************************************************************/
/*---- Function defintions -----------------------------------------------*/
 
  /* Definitions for the use of the representation of big integers */
 
 
    /************************************************************************/
    /* Make a new 'big' integer type with value 'val' (which must be less 
       than 1000 */
    struct big MakeLittleBig(int val);
 
 
    /************************************************************************/
    /* Outputs the value of the 'big' type 'x' to standard output. */
    void WriteBig(struct big x);
 
 
    /************************************************************************/
    /* Returns the boolean expression x=y */
    int IsEqual(struct big x, struct big y);
 
 
    /************************************************************************/
    /* 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);
 
 
    /************************************************************************/
    /* 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);
 
 
/**************************************************************************/
 
 
 
/**************************************************************************/
/*---- 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 -----------------------------*/
/**************************************************************************/

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:20


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