1. Overview

1.1. Computational Considerations for Recursive Fibonacci Weve 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) for n > 1

return fib(n - 1) + fib(n - 2);

}

This recursive function sports an exponential runtime. We saw in class that we can achieve linear runtime by building from our base cases, F(0) = 0 and F(1) = 1, toward our desired result, F(n). We thus avoid our expensive and exponentially EXplOsIVe recursive function calls. The former approach is called top-down processing, because we work from n down toward our base cases. The latter approach is called bottom-up processing, because we build from our base cases up toward our desired result, F(n). In general, the process by which we eliminate repetitive recursive calls by re-ordering our computation is called dynamic programming, and is a topic we will explore in more depth in COP 3503 (Computer Science II).

1.2. Representing Huge Integers in C Our 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 Cs 32-bit integer representation. On most modern systems, the maximum int value in C is 231-1, or 2,147,483,647.1 The first Fibonacci number to exceed that limit is F(47) = 2,971,215,073. Even Cs 64-bit unsigned long long int type is only guaranteed to represent non-negative integers up to and including 18,446,744,073,709,551,615 (which is 264-1).2 F(93) is 12,200,160,415,121,876,738, which can be stored as an unsigned long long int. However, F(94) is 19,740,274,219,868,223,167, which is too big to store in any of Cs extended integer data types. To overcome this limitation, we will represent integers in this program using linked lists, where each node holds a single digit of an integer.3 For reasons that will soon become apparent, we will store our integers in reverse order in these linked lists.

Storing these integers in reverse order makes it much easier to add two of them together than if we stored them the other way around. The ones digit for each integer is stored in the first node in its respective linked list, the tens digit is stored in the second node, the hundreds digit is stored in the third node, and so on. How convenient!

In this program, we will use this linked list representation for integers. The nodes will of course be allocated dynamically, and we will stuff the head of each linked list inside a struct that also keeps track of the lists length: typedef struct ListyInt

{

// The head of a linked list that holds the digits

// of an integer, stored in reverse order.

Node *head; // The number of digits in the integer (which is equal to the number of nodes in the list).

int length;

} ListyInt;

This struct is defined in ListyFib.h. There is, of course, a corresponding node struct defined in ListyFib.h, as well.

1.3. ListyFib.h (Super Important!) For your linked lists, you must use the ListyInt and Node structs we have specified in ListyFib.h without any modifications. Do not add those struct definitions to your code, though. Instead, you must #include the header file that contains those struct definitions by adding the following line of code to your ListyFib.c source file: #include "ListyFib.h"

Theres one final curve ball you have to deal with: there are a few places where your program will utilize unsigned integers. This is no cause to panic. An unsigned integer is just an integer that cant be negative. (Theres no sign associated with the value. Its always non-negative.) As weve seen in class, you declare an unsigned integer like so: unsigned int n;

Because an unsigned int is typically 32 bits (like the normal int data type), but doesnt need to use any of those bits to signify a sign, it can eke out a higher maximum positive integer value than a normal int. For at least one function in this assignment, youll need to know what the maximum value is that you can represent using an unsigned int on the system where your program is running. That value is defined in your systems limits.h file, which you should #include from your ListyFib.c source file, like so: #include

limits.h defines a value called UINT_MAX, which is the maximum value an unsigned int can hold. It also defines INT_MAX (the maximum value an int can hold), UINT_MIN, INT_MIN, and many others that you might want to read up on in your spare time. If you want to print an unsigned int, the correct conversion code is %u. For example:

unsigned int n = UINT_MAX;

printf("Max unsigned int value: %u ", n);

Note that (UINT_MAX + 1) necessarily causes integer overflow, but since an unsigned int cant be negative, (UINT_MAX + 1) just wraps back around to zero. Try this out for fun:

unsigned int n = UINT_MAX;

printf("Max unsigned int value (+1): %u ", n + 1);

Compare this, for example, to the integer overflow caused by the following: int n = INT_MAX;

printf("Max int value (+1): %d ", n + 1);

2. Function Requirements In the source file you submit, ListyFib.c, you must implement the following functions. You may implement any auxiliary functions you need to make these work, as well. Note that none of your functions should print to the screen, and the file you submit should not have a main() function.

ListyInt *listyAdd(ListyInt *p, ListyInt *q);

Description: Return a pointer to a new, dynamically allocated ListyInt struct that contains the result of adding the 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.

Another Special Note: If an argument passed to this function is non-NULL, you can assume that the head pointer inside that struct is also non-NULL and that the length is greater than zero. You may also assume that any non-NULL ListyInt struct passed to the functions in this assignment will be wellformed. For example, if the length field of a ListyInt is set to 3, the list will have exactly three nodes, and the last nodes next pointer will be set to NULL.

Runtime Restriction: The runtime of this function must be no worse than O(m + n), where m is the length of p, and n is the length of q.

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

ListyInt *destroyListyInt(ListyInt *listy);

Description: Destroy any and all dynamically allocated memory associated with listy in O(n) time (where n is the length of the list). Avoid segmentation faults and memory leaks.

Returns: NULL.

ListyInt *stringToListyInt(char *str);

Description: Convert a number from string format to ListyInt format in O(k) time (where k is the length of str). (For example function calls, see testcase01.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, but be careful to avoid memory leaks when you do so. You may assume the string will only contain ASCII digits 0 through 9, and that there will be no leading zeros in the string.

Returns: A pointer to the newly allocated ListyInt struct, or NULL if dynamic memory allocation fails or if str is NULL.

char *listyIntToString(ListyInt *listy);

Description: Convert the integer represented by listy to a dynamically allocated string, and return a pointer to that string (i.e., return the base address of the char array). Be sure to properly terminate the string with a null sentinel (\0). If listy is NULL, or if any calls to malloc() fail, simply return NULL. The runtime for this function must not exceed O(n) (where n is the length of the list).

Returns: A pointer to the dynamically allocated string, or NULL if dynamic memory allocation fails at any point or if listy is NULL.

ListyInt *uintToListyInt(unsigned int n);

Description: Convert the unsigned integer n to ListyInt format. If any dynamic memory allocation functions fail within this function, return NULL, but be careful to avoid memory leaks when you do so. Your runtime for this function cannot exceed O(k), where k is the number of digits in n.

Returns: A pointer to the newly allocated ListyInt struct, or NULL if dynamic memory allocation fails at any point.

unsigned int *listyIntToUint(ListyInt *listy);

Description: Convert the integer represented by listy to a dynamically allocated unsigned int, and return a pointer to that value. If listy is NULL, simply return NULL. If the integer represented by listy exceeds the maximum unsigned int value defined in limits.h, return NULL.

Note: The sole reason this function returns a pointer instead of an unsigned int is so that we can return NULL to signify failure in cases where listy cannot be represented as an unsigned int.

Returns: A pointer to the dynamically allocated unsigned integer, or NULL if the value cannot be represented as an unsigned integer (including the case where listy is NULL).

void plusPlus(ListyInt *listy);

Description: Increment the value held in listy by one. If listy is NULL, simply return. You dont necessarily have to use this function anywhere else in your program. Its just here as an additional exercise.

Special Note: If any dynamic memory allocation functions fail within this function, simply leave the value in listy unmodified. (Such a failure is unlikely anyway, and will not be explicitly tested for this particular function.)

Returns: Nothing. This is a void function.

ListyInt *fib(unsigned int n);

Description: This is your Fibonacci function. This is where the magic happens. Implement an iterative solution that runs in O(nk) time and returns a pointer to a ListyInt struct that contains F(n). (See runtime note below.) Be sure to prevent memory leaks before returning from this function.

Runtime Consideration: In the O(nk) runtime restriction, n is the parameter passed to the function, and k is the number of digits in F(n). So, within this function, you can make O(n) number of calls to any function that is O(k) (or faster).

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 to fib().

Special Notes: Notice that n will always be 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 a ListyInt representing F(n), or NULL if dynamic memory allocation fails.