Description
In this assignment, you will implement a number of small programs. Here, you will:
- use of dynamic memory allocation and pointers.
- Input validation should be performed. Hints on how to set the limits for validation are inside the text of the question.
Implementation Instructions
The HW3.tar.gz archives contains the file HW3.pdf (this file!) and the initial source code of the project. It also contains an output directory which contains the files that will be used to test your program. In the directory src/ you will find the following files:
- fib-main01.cpp, fib-main02.cpp, fib-main03.cpp, fib-main04.cpp, fib-main05.cpp are the tests for the implementation. They must not be modified.
- Fibonacci.cpp, Fibonacci.h implementation files.
You will submit:
1. only the source files (i.e., .cpp and .h files). Do not submit .o files, executables, or your test datasets.
2. files at point 1 (i.e. .cpp and .h files must be in the src directory compressed in the src.tar.gz file.
To compress src directory, move to its parent directory (i.e., if you are inside src, type cd ..), then type the following command on the linux terminal:
tar zcvf src . tar . gz src
Questions
In this programming assignment, you will implement a Fibonacci function that avoids repetitive computation by computing the sequence linearly from the bottom up:F(0) through F(n). You will also overcome the limitations of C/C++s 32-bit (or 64-bit) integers by storing very large integers in arrays of individual digits.
By completing this assignment, you will gain experience crafting algorithms of moderate complex- ity, develop a deeper understanding of integer type limitations, become acquainted with unsigned integers, and reinforce your understanding of dynamic memory management in C/C++. In the end, you will have a very fast and awesome program for computing huge Fibonacci numbers.
Representing Huge Integers
The 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/C++s 32-bit integer representation.
On most modern systems, the maximum int value in C/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. Even C/C++s 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 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. However, F(94) is 19,740,274,219,868,223,167, which is too big to store in any of C/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:
ure 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 index [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:
Figure 2: Calculating the sum of two numbers (LSD first) see image.
In this program, we will use this array representation for integers. The arrays will be allocated dynamically, and we will stuff each array inside a struct that also keeps track of the arrays length:
struct HugeInteger
{
// a dynamically allocated array to hold the digits
// of a huge integer , stored in reverse order
int ∗digits ;
// the number of digits in the huge integer (which is
// approximately equal to the length of the array)
int length ;
};
Function Requirements
In the source file you submit, Fibonacci.cpp, 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.
- HugeInteger *hugeAdd(const HugeInteger *p, const HugeInteger *q);
Description: Return a pointer to a new, dynamically allocated HugeInteger struct that contains the result of adding the huge 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. You might find it helpful to make the array slightly larger than is absolutely necessary in some cases. As long as that extra overhead is bounded by a very small constant, thats okay. (In this case, the structs length field should reflect the number of meaningful digits in the array, not the actual length of the array, which will necessarily be a bit larger.)
Returns: A pointer to the newly allocated HugeInteger struct, or NULL in the special cases mentioned above.
- HugeInteger *hugeDestroyer(HugeInteger *p);
Description: Destroy any and all dynamically allocated memory associated with p. Avoid segmentation faults and memory leaks.
Returns: NULL
- HugeInteger *parseString(const char *str);
Description: Convert a number from string format to HugeInteger format. (For example function calls, see fib-main01.cpp.)
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 HugeInteger struct, or NULL if dynamic memory allocation fails or if str is NULL.
- HugeInteger *parseInt(unsigned int n);
Description: Convert the unsigned integer n to HugeInteger format.
Special Notes: 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 the newly allocated HugeInteger struct, or NULL if dynamic memory allocation fails at any point.
- unsigned int *toUnsignedInt(const HugeInteger *p);
Description: Convert the integer represented by p to a dynamically allocated unsigned int, and return a pointer to that value. If p is NULL, simply return NULL. If the integer represented by p exceeds the maximum unsigned int value defined in limits.h, return NULL.
Special Notes: 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 p 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 p is NULL).
- HugeInteger *fib(int n);
Description: This is your Fibonacci function; this is where the magic happens. Implement an iterative solution that runs in O(n) time and returns a pointer to a HugeInteger 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 fib().
Special Notes: 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 a HugeInteger representing F(n), or NULL if dynamic memory allocation fails.
- double difficultyRating(void);
Returns: A double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult).
- double hoursSpent(void);
Returns: An estimate (greater than zero) of the number of hours you spent on this assign- ment.
