CMSC 205

DATA STRUCTURES AND ALGORITHMS I

PROJECT 4

LARGE-NUMBER ARITHMETIC

DUE: 4/2/2017

BACKGROUND

The size of a number that can be stored in computer memory is limited by the word size of the particular system being used. For example, the largest positive integer that can be stored in a 16-bit word is 32767. The largest positive integer that can be stored in a 32-bit word is 2,147,483,647. In some applications (e.g. keeping track of the national debt), it obviously is necessary to process integers that are larger than this value. Integers that are larger than the word size of the computer are called large integers.

PROBLEM

Create a class for the ADT LargeInteger given the data structure and methods given below.

DATA STRUCTURE

Large integers will be represented as a doubly linked list with a head node. Each list node will store 3 digits of the large integer. The sign of the large integer will be stored in the head node as +1 for a positive large integer or -1 for a negative large integer. A large integer with a value of zero is stored as a positive zero. Therefore, the integer A = 72,456,103,046 is represented as:

head		1			72			456			103			046

THE LargeInteger CLASS

The class must be called LargeInteger. It must contain the following methods with the given method names.

void readLI()

This method will prompt the user to enter a large integer. The large integer is of the form: an optional positive sign (+) or a negative sign followed by a groups of three digits separated by commas. The first group may have less than three digits. The following are examples of the input forms.

72,456,103,046

+72,456,103,046 -72,456,103,046

Example method call: aLI.readLI();

void writeLI()

This method will output the large integer in blocks of three digits separated by spaces, for example, 72 456 103 046. Note that the first block has no leading zeros if the first block has a value less than 100. All other blocks must have leading zeros present when the block has a value less than 100.

Example method call: aLI.writeLI();

void zeroLI()

This method sets the object to a zero large integer as described above under Data Structure.

Example method call: aLI.zeroLI();

LargeInteger addLI(LargeInteger operand2)

This method adds the large integer object of the add to the operand2 object argument and returns the sum as a new large integer object.

Example method call: sum = operand1.addLI(operand2);

LargeInteger subLI(LargeInteger operand2)

This method subtracts from the large integer object of the sub, the operand2 object argument and returns the difference as a new large integer object.

Example method call: diff = operand1.subLI(operand2);

LargeInteger multLI(LargeInteger operand2)

This method multiplies the large integer object of the multiplication by the operand2 object argument and returns the product as a new large integer object.

Example method call: product = operand1.multLI(operand2);

LargeInteger assignLI()

This method returns a copy of the large integer object.

Example method call: bLI = aLI.assignLI();

boolean eqLI(LargeInteger operand2)

This method returns true if the large integer object is equal to the operand2 object argument; otherwise the method returns false.

Example method call: operand1.egLI(operand2);

boolean geqLI(LargeInteger operand2)

This method returns true if the large integer object is greater than or equal to the operand2 object argument; otherwise the method returns false.

Example method call: operand1.geqLI(operand2);

SCORING

Your 50 result points and 20 specifications will be combined to score your method implementations as follows:

writeLI, zeroLI, eqLI, geqLI:	6 points each
readLI, assignLI:	8 points each
addLI, subLI, multLI:	10 points each

TESTING

You should test your class thoroughly by writing a driver program. I will test your class with my own driver program to check that your methods work as intended. A deduction of 10 points will be made if your program does not link up with my driver without error.

Output should be as follows

OUTPUT:

Enter the rows and columns in the wall: 13 9

|-----------------------------------------------------------------------------------------------|

| Paint Ball Simulation | Results |

|-----------------------------------------------------------------------------------------------|

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ROW TOTALS |

| 1 4/4 | 2/6 | 0/8 | 4/4 | 3/5 | 1/12 | 4/7 | 0/7 | 2/2 | 20/55 |

| 2 2/6 | 2/9 | 2/5 | 1/8 | 0/11 | 5/9 | 6/11 | 1/10 | 2/4 | 21/73 |

| 3 0/5 | 3/9 | 2/8 | 2/6 | 2/6 | 2/10 | 1/11 | 2/5 | 1/6 | 15/66 |

| 4 0/8 | 5/5 | 1/10 | 1/5 | 2/10 | 2/5 | 1/5 | 2/9 | 2/6 | 16/63 |

| 5 3/2 | 1/14 | 2/5 | 0/12 | 5/4 | 0/9 | 0/6 | 4/7 | 3/7 | 18/66 |

| 6 1/9 | 4/7 | 3/13 | 4/6 | 2/13 | 2/4 | 1/6 | 2/6 | 1/8 | 20/72 |

| 7 2/5 | 2/11 | 3/8 | 1/10 | 2/5 | 1/7 | 2/4 | 0/7 | 3/3 | 16/60 |

| 8 2/6 | 2/6 | 2/8 | 1/5 | 1/4 | 1/4 | 2/3 | 0/6 | 2/6 | 13/48 |

| 9 2/2 | 0/7 | 2/7 | 1/5 | 0/4 | 0/1 | 0/4 | 2/6 | 3/6 | 10/42 |

| 10 0/3 | 1/4 | 4/7 | 2/7 | 2/3 | 0/3 | 0/6 | 3/5 | 2/8 | 14/46 |

| 11 0/2 | 0/5 | 2/7 | 0/5 | 1/6 | 1/6 | 3/4 | 1/11 | 2/7 | 10/53 |

| 12 2/2 | 2/7 | 3/8 | 0/7 | 3/4 | 2/8 | 2/10 | 3/8 | 4/7 | 21/61 |

| 13 0/4 | 2/6 | 4/6 | 1/5 | 1/6 | 2/5 | 2/5 | 1/7 | 2/5 | 15/49 |

|-----------------------------------------------------------------------------------------------|

Do Another Simulation (Y/N): Y

Enter the rows and columns in the wall: 13 9

|-----------------------------------------------------------------------------------------------|

| Paint Ball Simulation | Results |

|-----------------------------------------------------------------------------------------------|

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ROW TOTALS |

| 1 2/1 | 1/5 | 0/3 | 1/3 | 2/5 | 1/8 | 3/3 | 0/4 | 1/0 | 11/32 |

| 2 0/5 | 3/2 | 1/6 | 1/7 | 3/9 | 3/9 | 2/7 | 0/4 | 0/2 | 13/51 |

| 3 0/2 | 0/7 | 2/5 | 2/7 | 3/8 | 3/7 | 1/8 | 2/2 | 1/2 | 14/48 |

| 4 2/5 | 2/4 | 2/8 | 1/5 | 0/5 | 0/5 | 1/2 | 0/5 | 0/2 | 8/41 |

| 5 3/3 | 0/10 | 3/3 | 1/6 | 1/5 | 1/3 | 1/6 | 2/3 | 1/4 | 13/43 |

| 6 1/5 | 2/3 | 0/6 | 1/4 | 3/4 | 1/8 | 2/3 | 1/7 | 2/2 | 13/42 |

| 7 0/4 | 2/3 | 0/4 | 0/5 | 1/7 | 2/3 | 0/6 | 1/1 | 0/3 | 6/36 |

| 8 1/2 | 1/6 | 2/5 | 3/6 | 2/7 | 1/6 | 1/4 | 0/3 | 0/1 | 11/40 |

| 9 1/3 | 1/4 | 1/6 | 2/7 | 2/6 | 1/7 | 3/3 | 1/4 | 1/1 | 13/41 |

| 10 1/3 | 1/5 | 1/4 | 1/5 | 1/5 | 1/3 | 0/4 | 0/1 | 0/3 | 6/33 |

| 11 1/6 | 2/3 | 1/6 | 1/4 | 1/4 | 1/3 | 0/2 | 0/4 | 2/1 | 9/33 |

| 12 3/2 | 0/7 | 2/3 | 1/5 | 1/3 | 1/5 | 1/6 | 2/2 | 1/7 | 12/40 |

| 13 1/3 | 0/2 | 1/3 | 1/2 | 0/4 | 2/4 | 3/3 | 0/8 | 3/1 | 11/30 |

|-----------------------------------------------------------------------------------------------|

Do Another Simulation (Y/N): N