In this programming assignment, you will implement a Fibonacci function that avoids repet- itive computation by computing the sequence linearly from the bottom up: F(0) through F(n). You will also overcome the limitations of C's 32-bit integers by storing very large integers in arrays of individual digits.
By completing this assignment, you will gain experience crafting algorithms of moderate com- plexity, develop a deeper understanding of integer type limitations, become acquainted with unsigned integers, and reinforce your understanding of dynamic memory management in C. In the end, you will have a very fast and awesome program for computing huge 50 decimal digit sequences of Fibonacci numbers.
Interestingly, this problem will be limited to 50 decimal digit numbers, from the outset, thru the whole program. This will mimic the performance constraints of some old cryptographic equipment (KW-26) that generated key strings based on a 2 number input to start a continuous chain of some type of calculations to generate long apparently random number sequences.
big50.h, big50-main{01-04}.c, big50-main{01-04}.log, big50-main04.err
big50.c
We've seen in class that calculating Fibonacci numbers with the most straightforward recursive implementation of the function is prohibitively slow, as there is a lot of repetitive computation:
int fib(int n)
{
//base cases: F(0) = 0, F(1) = 1
if (n < 2)
return n;
//definition of Fibonacci: F(n) = F(n - 1) + F(n - 2)
return fib(n - 1) + fib(n - 2);
}
This recursive function sports an exponential runtime. It is possible to achieve linear runtime by building from the base cases, F(0) = 0 and F(1) = 1, toward the desired result, F(n). This avoids the expensive and exponentially explosive recursive function calls.
This assignment will emulate some aspects of hardware encryption from the 1960s, specifically the KW-26, while the KW-26 used 45 digit round-robin counters and a bit of other hardware, this as- signment will use 50 decimal digit counters, with two initialization vectors, the cryptoVariable and the hwConfigVariable. Each of these vectors will be 50 decimal digits. All subsequent products will be 50 decimal digits. In the event of overflow the overflow product will be ignored.
Once the cryptoVariable and the hwConfigVariable have been read and created, respectively, they will be decimally added to produce a Fibonacci sum. All subsequent 50 digit integers will be the sum of the two previous 50 digit integers. (This ensures that the digits after F(2) will be unique and the full 50 digits.) The math is shown below.
f 0 = hwConfigV ariable
f 1 = cryptoV ariable
f 2 = f 1 + f 0
.
.
.
f n = f n−1 + f n−2
Note that 50 decimal digits does not fit into any standard C variable data type. (See Section 7, Representing huge integers in C for a detailed explanation on how to add large integers using a created data type.)
Careful review shows that by placing the 50 decimal digit integers into an array, with the least significant digit in the leading digit it will be possible to add the two 50 digit numbers together, if added one digit at a time from the first element in the array to the last element in the array. Arithmetically speaking the most significant digit will be in the most significant slot in the array.
For example, the decimal number 12,567 would be parsed one digit at a time into an array named x containing 7 in x[0], 6 in x[1], 5 in x[2], 2 in x[3], and 1 in x[4]. All 50 decimal digits will be stored in an array using the following data structure to hold the pointer to the malloced buffer of 50 digits.
typedef struct Integer50
{
// a dynamically allocated array to hold a 50
// digit integer, stored in reverse order
int *digits;
} Integer50;
This assignment includes a header file, big50.h, which contains the definition for the Integer50 struct, as well as functional prototypes for all the required functions in this assignment. You should #include this header file from your big50.c source file, like so:
#include "big50.h"
This assignment comes with multiple sample main files (big50-main01-04.c), which you can compile with your big50.c source file. For more information about compiling projects with multi- ple source files, see Section 5, Compilation and Testing (Linux/Mac Command Line).
Also included are a number of sample output files that show the expected results of executing your program (big50-main01-04.log &big50-main04.err).
The test cases included with this assignment are by no means comprehensive. Please be sure to develop your own test cases, and spend some time thinking of edge cases that might break each of the required functions.
In the source file you submit, big50.c, you must implement the following functions. You may im- plement any auxiliary functions you need to make these work, as well. Notice that none of your functions should print anything to the screen or STDOUT.
Integer50 *big50Add(Integer50 *p, Integer50 *q);
Description: Return a pointer to a new, dynamically allocated Integer50 struct that contains the result of adding the 50 digit integers represented by p and q.
Special Notes: If a NULL pointer is passed to this function, simply return NULL. If any dy- namic memory allocation functions fail within this function, also return NULL, but be care- ful to avoid memory leaks when you do so.
Hint: Before adding two huge integers, you will want to create an array to store the result. Re- member that all integers in this problem are 50 digits long. In the event that the most sig- nificant digits (MSD) result in a carry, the carry will be ignored. For example, if the MSD of the two inputs are 9 and 7, the resultant MSD will be 6 with a carry of 1 for the MSD + 1 digit. (9 + 7 = 16, therefore 6 is the MSD and the 1 is ignored.)
Returns: A pointer to the newly allocated Integer50 struct, or NULL in the special cases men- tioned above.
Integer50 *i50Destroyer(Integer50 *p);
Description: Destroy any and all dynamically allocated memory associated with p. Avoid seg- mentation faults and memory leaks.
Returns: NULL
Integer50 *parseString(char *str);
Description: Convert a number from string format to Integer50 format. (For example function calls, see big50-main01.c.)
Special Notes: If the empty string () is passed to this function, treat it as a zero (0). If any dynamic memory allocation functions fail within this function, or if str is NULL, return NULL, be careful to avoid memory leaks when you do so. You may assume the string will only contain ASCII digits 0 through 9, for a minimum of 50 digits. In the event that 50 digits are not in the input string, print an error message to STDERR and fill with leading zeroes. Also, if there are more than 50 digits in the input string use the first 50 digits in the string.
Returns: A pointer to the newly allocated Integer50 struct, or NULL if dynamic memory alloca- tion fails or if the input str is NULL.
Integer50 *fibBig50(int n, Integer50 *first, Integer50 *second);
Description: This is your Fibonacci function. Pay careful attention the F(0) is initialized with the hwConfigVariable and F(1) is initialized with the cryptoVariable. Implement an itera- tive solution that runs in O(n) time and returns a pointer to a Integer50 struct that contains F(n). Be sure to prevent memory leaks before returning from this function.
Space Consideration: When computing F(n) for large n, its important to keep as few Fibonacci numbers in memory as necessary at any given time. For example, in building up to F(10000), you wont want to hold Fibonacci numbers F(0) through F(9999) in memory all at once. Find a way to have only a few Fibonacci numbers in memory at any given time over the course of a single call to fibBig50(...).
Special Notes: Remember that n is the second parameter passed as an input argument to the program. You may assume that n is a non-negative integer. If any dynamic memory alloca- tion functions fail within this function, return NULL, but be careful to avoid memory leaks when you do so.
Returns: A pointer to an Integer50 representing F(n), or NULL if dynamic memory allocation fails.
void big50Rating();
STDERR output: Outputs the following items to STDERR, delimited by a semicolon ;:
1. NID
2. A difficulty rating of how difficult you found this assignment on a scale of 1.0 (ridicu- lously easy) through 5.0 (insanely difficult).
3. Duration, in hours, of the time you spent on this assignment.
The first argument to this function is the pointer to the big50RatingStruct which is defined in the big50.h include file. Make sure to output those items to STDERR. Each element should be terminated or delimited by a ;.
Integer50* loadHwConfigVariable(int seed);
Returns: A pointer to an Integer50 array of 50 random digits. If the input variable seed is set, the random number generator will be seeded, otherwise not. Regardless, the 50 digits will be initialized in 10 unique groups of 5 random digits. Returns NULL if there is an error during creation or initialization of the hwConfigVariable.
Integer50* loadCryptoVariable(char *cryptoVariableFilename);
Returns: A pointer to an Integer50 array of 50 random digits read in from the cryptoVariable- Filename. Returns NULL if there is an error during initialization of the cryptoVariable or in the file I/O.
To compile multiple source files (.c files) at the command line:
gcc big50.c big50-main01.c
By default, this will produce an executable file called a.out that you can run by typing, e.g.:
./a.out
If you want to name the executable something else, use:
gcc big50.c big50-main01.c -o b50-01.exe
...and then run the program using:
./b50-01.exe
Running your program could potentially dump a lot of output to the screen. If you want to redi- rect your output to a text file in Linux, its easy. Just run the program using the following:
./b50-01.exe > whatever.txt
This will create a file called whatever.txt that contains the output from your program.
Linux has a helpful command called diff for comparing the contents of two files, which is really helpful here since weve provided sample output files. You can see whether your output matches ours exactly by typing, e.g.:
diff whatever.txt b50-output01.txt
If the contents of whatever.txt and b50-output01.txt are exactly the same, diff wont have any output. It will just look like this:
mcalpin@eustis:~$ diff whatever.txt b50-output01.txt
mcalpin@eustis:~$ _
If the files differ, it will spit out some information about the lines that arent the same. For exam- ple:
mcalpin@eustis:-$ diff big50-main02.log big50-main02.bogus.log
2c2
< 19427194271942719427194271942719427194271942719427
---
> 49427194271942719427194271942719427194271942719427
mcalpin@eustis:~$ _
Any linear Fibonacci function has a big problem, though, which is perhaps less obvious than the original runtime issue: when computing the sequence, we quickly exceed the limits of C's 32-bit integer representation. On most modern systems, the maximum int value in C is 2 32 1, or 2,147,483,647. 1 The first Fibonacci number to exceed that limit is F(47) = 2,971,215,073. Ob- viously, this will not support a 50 digit number calculation.
This problem is exacerbated by the fact that all the numbers used in this problem will be 50 deci- mal digits long. The maximum value of 10 50 requires 163 bits. The 163 bits is derived by solving the following equation: see image.
Even C's 64-bit unsigned long long int type is only guaranteed to represent non-negative in- tegers up to and including 18,446,744,073,709,551,615 which is 2 64 1. 2 The Fibonacci number F(93) is 12,200,160,415,121,876,738, which can be stored as an unsigned long long int. How- ever, F(94) is 19,740,274,219,868,223,167, which is too big to store in any of C's extended integer data types.
To overcome this limitation, we will represent integers in this program using arrays, where each index holds a single digit of an integer. 3 For reasons that will soon become obvious, we will store integers in reverse order in these arrays. So, for example, the numbers 2,147,483,648 and 10,0087 would be represented as:
Figure 1: Two numbers stored in array - LSD first. see image.
Storing these integers in reverse order makes it really easy to add two of them together. The ones digits for both integers are stored at index [0] in their respective arrays, the tens digits are at in- dex [1], the hundreds digits are at index [2], and so on. How convenient!
So, to add these two numbers together, we add the values at index [0] (8 + 7 = 15), throw down the 5 at index [0] in some new array where we want to store the sum, carry the 1, add it to the values at index [1] in our arrays (1 + 4 + 8 = 13), and so on:
Note that the examples shown are for small sequences of digits. For all numbers in this program, we will use this array representation for integers containing 50 digits. The arrays will be allocated dynamically.
Figure 2: Calculating the sum of two numbers (LSD first) see image.