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 8
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_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
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_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 157
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
====== 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 [[http://www.n-e-x.co.uk/files/fib2.zip|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
#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
#include
#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.
--- //[[nex@n-e-x.co.uk|Nexami Engeo]] 2007/07/05 17:20//
~~DISCUSSION~~