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