1 Overview 1.1 Computational Considerations for Recursive Fibonacci 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, speci?cally the KW-26, while the KW-26 used 45 digit round-robin counters and a bit of other hardware, this assignment will use 40 hexadecimal digit counters, with two initialization vectors, the cryptoVariable and the hwCon?gVariable. Each of these vectors will be 40 hexadecimal digits. All subsequent products will be 40 hexadecimal digits. In the event of over?ow the over?ow product will be ignored. Once the cryptoVariable and the hwCon?gVariable have been read and created, respectively, they will be decimally added to produce a Fibonacci sum. All subsequent 40 hexadecimal digit integers will be the sum of the two previous 40 hexadecimal digit integers. (This ensures that the digits after F(2) will be unique and the full 40 digits.) The math is shown below. f0 = hwConfigV ariable f1 = cryptoV ariable f2 = f1 +f0 . . . fn = fn?1 +fn?2 Note that 40 hexadecimal digits does not ?t 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 40 hexadecimal digit integers into an array, with the least signi?cant digit in the leading digit it will be possible to add the two 40 digit numbers together, if added one digit at a time from the ?rst element in the array to the last element in the 2 array. Arithmetically speaking the most signi?cant digit will be in the most signi?cant 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 40 hexadecimal digits will be stored in an array using the following data structure to hold the pointer to the malloced bu?er of 40 digits.

Structure is not changeable.

typedef struct Integer40 {

// a dynamically allocated array to hold a 40

// digit integer, stored in reverse order

int *digits;

} Integer40; 2 Attachments 2.1 Header File (big40.h) This assignment includes a header ?le, big40.h, which contains the de?nition for the Integer40 struct, as well as functional prototypes for all the required functions in this assignment. You should #include this header ?le from your big40.c source ?le, like so: #include "big40.h" 2.2 Test Cases This assignment comes with multiple sample main ?les (big40-main01-04.c), which you can compile with your big40.c source ?le. For more information about compiling projects with multiple source ?les, see Section 5, Compilation and Testing (Linux/Mac Command Line). 2.3 Sample Output Files Also included are a number of sample output ?les that show the expected results of executing your program (big40-main01-04.log & big40-main04.err). 2.4 Disclaimer 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. 3 Function Requirements In the source ?le you submit, big40.c, you must implement the following functions. You may implement 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. Integer40

*big40Add(Integer40 *p, Integer40 *q); Description: Return a pointer to a new, dynamically allocated Integer40 struct that contains the result of adding the 40 digit integers represented by p and q.

Special Notes: If a NULL pointer is passed to this function, simply return NULL. If any dynamic memory allocation functions fail within this function, also return NULL, but be careful 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. Remember that all integers in this problem are 40 digits long. In the event that the most signi?cant 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. (916 +716 =1016, therefore 6 is the MSD and the 1 is ignored.)1

Returns: A pointer to the newly allocated Integer40 struct, or NULL in the special cases mentioned above.

Integer40 *i40Destroyer(Integer40 *p);

Description: Destroy any and all dynamically allocated memory associated with p. Avoid segmentation faults and memory leaks. Returns: NULL

Integer40 *parseString(char *str);

Description: Convert a number from string format to Integer40 format. (For example function calls, see big40-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 and the letters A thru F in either upper or lower case, for a minimum of 40 digits. In the event that 40 digits are not in the input string, print an error message to STDERR and ?ll with leading zeroes. Also, if there are more than 40 digits in the input string use the ?rst 40 digits in the string.

Returns: A pointer to the newly allocated Integer40 struct, or NULL if dynamic memory allocation fails or if the input str is NULL. 1The subscript of 16 indicate base 16. However the two expressions 1016 and 10x are equivalent and used equally often. Integer40 *fibBig40(int n, Integer40 *first, Integer40 *second); Description: This is your Fibonacci function. Pay careful attention the F(0) is initialized with the hwCon?gVariable and F(1) is initialized with the cryptoVariable. Implement an iterative solution that runs in O(n) time and returns a pointer to a Integer40 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 ?bBig40(...). 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 allocation functions fail within this function, return NULL, but be careful to avoid memory leaks when you do so.

Returns: A pointer to an Integer40 representing F(n), or NULL if dynamic memory allocation fails. Integer40* loadHwConfigVariable(int seed); Returns: A pointer to an Integer40 array of 40 random digits. If the input variable seed is set, the random number generator will be seeded, otherwise not. Regardless, the 40 digits will be initialized in 10 unique groups of 4 random digits.

Returns NULL if there is an error during creation or initialization of the hwCon?gVariable.

Integer40* loadCryptoVariable(char *cryptoVariableFilename); Returns: A pointer to an Integer40 array of 40 random digits read in from the cryptoVariableFilename. Returns NULL if there is an error during initialization of the cryptoVariable or in the ?le I/O.

?