I need help with a program that will be designed to run the Fibonacci sequence (WITHOUT USING RECURSION) to be able to achieve O(n) while calculating with 50 digits. I am having trouble writing some of the functions which are outlined below:

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, specifically the KW-26, while the KW-26 used 45 digit round-robin counters and a bit of other hardware, this assignment 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. f0 = hwConfigV ariable f1 = cryptoV ariable f2 = f1 + f0 ... fn = fn1 + fn2 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;

2 Attachments

2.1 Header File (big50.h) 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"

2.2 Test Cases 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 multiple source files, see Section 5, Compilation and Testing (Linux/Mac Command Line).

2.3 Sample Output Files 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).

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 file you submit, big50.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.

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 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 50 digits long. In the event that the most significant 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 mentioned above.

Integer50 *i50Destroyer(Integer50 *p); Description: Destroy any and all dynamically allocated memory associated with p. Avoid segmentation 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 allocation 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 iterative 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 allocation 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 (ridiculously 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.