Programming Assignment

CptS 122 - Data Structures

Programming Assignment 7: Big Integer

Assigned: Friday, October 26, 2012

Due: Friday, November 16, 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

III. Overview & Requirements:

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 by converting it 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. BigInt* Add(BigInt& lhs, BigInt& rhs) – Creates and returns a BigInt object that is equal to (lhs + rhs).

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

Update Nov. 8: PA8 will be a continuation of PA7 and will require you to do multiplication and division. If you already started those, do not delete them thinking that they won’t be needed!

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
All results of expressions in the test file will be positive. This means that all subtractions will satisfy: lhs >= rhs
Windows line breaks will be used between lines ("\r\n")

Sample input file:

4737+7161406428

2147483647+1

64123321123-52123321123

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:

7161411165

2147483648

12000000000

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. For example, consider the pseudo-code for addition:

let output = empty_string

let carry = 0

while (digitsLeftToProcess)

  digit1 = rightmost unprocessed digit of operand A

  digit2 = rightmost unprocessed digit of operand B

  let sum = digit1 + digit2 + carry

  // Determine the carry for the next digit

  carry = sum / 10

  // Copy the digit to the left of all exiting digits in output

  setDigitInOutput(sum % 10)

return output;

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:

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>_pa7.zip by the due date and time.
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.
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 add and subtract operations. In other words, 50% of the lines will be additions, and 50% subtractions (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 7 methods. The arithmetic ones are the only ones that are permitted to be not implemented, but they still must be present. You must have the constructor, destructor, and ToString methods present and correct.

10 points will be determined from your adherence to proper programming style established for the class and comments