CptS 122 - Data Structures                                                                                              

Programming Assignment 8: Big Integer (continued)

Assigned: Friday, November 16, 2012

Due: Monday, December 3, 2012 by midnight

I. Learner Objectives:

At the conclusion of this programming assignment, participants should be able to:

• Understand precision limitations in the C++ “int” type
• Implement C++ classes that store data that can grow without limitation (besides machine memory constraints)
• Understand how to convert basic algebraic procedures to algorithms
• Parse simple arithmetic expressions from strings and evaluate them

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

• Write C++ classes
• Be familiar with C++ class terminology
• Understand dynamic allocation and the concept of dynamic arrays
• Complete the previous PA7 assignment

III. Overview & Requirements:

This assignment is a continuation of PA7. It is recommended that you make a copy of your PA7 assignment and build on top of that for PA8.

The int data type in C/C++ is (typically) 32-bits in size. This means that there are 2³² = 4,294,967,296 possible integer values that can be represented by an int. While this is more than enough for many types of applications, there are other types of applications that require a much wider range than this. In fact, some applications may need to store numbers that have the number of bits that are used to store the data value change dynamically.  For this assignment you will create a C++ class named “BigInt” that can store an integer value with unlimited precision. Your class must be able to store any integer value that can fit within memory. You can approach this problem in one of two ways:

• Use an array of char digit values to store numerical data, which is equivalent to storing the number as a string.
• OR
• Use an array of unsigned char values to store the number in binary form. You may choose to use two’s complement for negative numbers, or use a separate bool member variable to keep track of negative or positive.

Write a C++ class that allows for arithmetic operations on large integer values. You cannot use the int data type to store the number internally. Implement the following member functions in this class:

1.    BigInt(const char* str) – Constructor that initializes the value of the BigInt from a string.

2.    ~BigInt() – Destructor that frees all dynamically allocated data used by the object and sets internal pointers to null.

3.    char* ToString() – Dynamically allocates and returns a copy of the BigInt as a string. Note that if you are choosing to store the number as a string internally, then this must make a copy of that string and return it. Otherwise this method is expected to produce a decimal string from your binary data. The caller of the function is expected to free the string using delete[] when finished with it.

Include the following static functions in your BigInt class as well:

4.    static BigInt* Add(BigInt& lhs, BigInt& rhs) – Creates and returns a BigInt object that is equal to (lhs + rhs).

5.    static BigInt* Subtract(BigInt& lhs, BigInt& rhs) – Creates and returns a BigInt object that is equal to (lhs – rhs).

6.    static BigInt* Multiply(BigInt& lhs, BigInt& rhs) – Creates and returns a BigInt object that is equal to (lhs * rhs).

7.    static BigInt* Divide(BigInt& lhs, BigInt& rhs) – Creates and returns a BigInt object that is equal to (lhs / rhs).

or if you prefer:

7.    static BigInt* Divide(BigInt& lhs, BigInt& rhs, BigInt** outRemainder) – Creates and returns a BigInt object that is equal to (lhs / rhs) and also fills a remainder value.

You must have these methods. They are to dynamically allocate and return the proper BigInt object, which must be deallocated (using delete) by the caller. You can add as many additional private methods as you want to serve as helper functions.

Your program will perform arithmetic operations stored in an input file and write results to an output file. When your program runs, take the first argument as the input file name and open it for reading. Take the second argument as the output file name and open it for writing. Details of the input file format follow:

• There will be a single binary operation per line.
• There will not be any spaces on a line.
• The numbers will NOT contain commas for thousand separators.
• The numbers will all be valid integers for your BigInt class. In other words there will not be "trick" lines to try to mess up your code. Robust code is important, but the main focus of this assignment is C++ classes and BigInt algorithms.
• All numbers in the input file will be positive.
• Windows line breaks will be used between lines ("\r\n").

Sample input file:

123456789*987654321

987654321/123456789

123456789123456*10000000001

Your output file must contain numerical results for these operations, one per line. If you do not get around to implementing an operator, you code must look for it regardless and write a line saying “(not implemented)” to the output file. Therefore regardless of how far you get in the assignment, the output file you produce should have the same number of lines as the input file.

The sample output file for this input file would be:

Sample output file:

121932631112635269

8

1234567891358016789123456

Your main function may start something like this:

int main(int argc, char* argv[])

{

if (argc < 3)

       {

return 1;

       }

// Open the input and output files

       FILE* input = fopen(argv[1], "r");

       FILE* output = fopen(argv[2], "w");

// Read lines from the input file, parse them as arithmetic operations, compute the result,

// and store it on a line in the output file

// YOUR CODE HERE

return 0;

}

You can use a different method of file I/O if you like, just make sure you use argv[1] as the input file name and argv[2] as the output file name.

Though this assignment may seem complex at first, realize that you already know the algorithms for each of the arithmetic operations. Since grade school you've had the ability to add, subtract, multiply, and divide numbers by hand. Think of the step-by-step processes that you use when doing arithmetic by hand and translate those to algorithms.

Some final requirements/recommendations are as follows:

• Do NOT put separating commas in your output numbers, nor should you expect them in the input numbers.

• Start by implementing all member functions and have them just write the “(not implemented)” line to the file. Run tests at this point just to make sure your code always produces an output file with the same number of lines as the input file. An automated grading program will be used to determine your score, and it will not know what operations you skipped if you have fewer lines in your output file than in the input file.

• Do not use the functions atoi or itoa in this assignment. They are for use with 32-bit integers and are not applicable here.

• Do not add extra spaces, tabs, or line breaks to the file. Write the resulting number starting at the first character of the line and write the ‘\n’ line break right after the last digit.

• If the input/output argument strings are not used and you instead use hard-coded file names, you will receive a 0 for the assignment.

IV. Submitting Assignments:

1. Using the Angel tool https://lms.wsu.edu submit your assignment to your TA. You will "drop" your solution into the provided "Homework Submissions" Drop Box under the "Lessons" tab. You must upload your solutions as <your last name>_pa8.zip by the due date and time.
2. Your .zip file should contain one project workspace. You can delete the “Debug” folders and any .ncb files before creating your zip. They are not needed.
3. Your projects must build properly. Any assignment that does not build properly receives a grade of 0.

V. Grading Guidelines:

This assignment is worth 100 points. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria:

• 80 points will be determined by the percentage of correct lines in your output file

o So if your output file is examined and you got 70% of operations correct, then you get 0.7 * 80 = 56 points out of 80 for this part

o The input file used for grading will contain the same number of multiply and divide operations. In other words, 50% of the lines will be multiplications, and 50% divisions (but they can be in any order).

• 10 points will be determined from an examination of your code and a check that you have all required methods.

• 10 points will be determined from your adherence to proper programming style established for the class and comments.
• BONUS: Up to 10 possible points for code that properly handles negative values