CSCI 241 - Homework 8:
additup revisited

Due by 11:59.59pm Wednesday, 17 Dec 2008

Introduction

For this assigment, we will be revisiting arbitrary precision integers. You will be creating a BigInteger class that uses a vector (or a deque or other similar STL Container) as the backing storage for the digits. In addition to addition, you'll be supporting comparison operators and multiplication by an unsigned long.

Partners

You are allowed to work with a partner on this assignment if you choose. However, pairs are encouraged to also implement full BigInteger multiplication.

BigInteger class

I want you to create 2 files BigInteger.h and BigInteger.cpp to contain your class. Users should be able to include the header file for compilation purposes and then link it against your compiled BigInteger.cpp object to get the functionality.

You need to implement the following member functions in your class:

Constructors

• BigInteger( int value = 0 );
• BigInteger( string value );

Assignment operators

• const BigInteger & operator+=( const BigInteger & rhs );
• const BigInteger & operator*=( const unsigned long rhs );
• const BigInteger & operator*=( const BigInteger & rhs ); ( optional )

Named member functions

• bool isZero( ) const;
• void print( ostream & out = cout ) const;

And these functions will need to be outside of the class:

Binary mathematical operators

• BigInteger operator+( const BigInteger & lhs, const BigInteger & rhs );
• BigInteger operator*( const BigInteger & lhs, const unsigned long rhs );
• BigInteger operator*( const BigInteger & lhs, const BigInteger & rhs ); ( optional )

Relational operators

• bool operator< ( const BigInteger & lhs, const BigInteger & rhs );
• bool operator<=( const BigInteger & lhs, const BigInteger & rhs );
• bool operator> ( const BigInteger & lhs, const BigInteger & rhs );
• bool operator>=( const BigInteger & lhs, const BigInteger & rhs );
• bool operator==( const BigInteger & lhs, const BigInteger & rhs );
• bool operator!=( const BigInteger & lhs, const BigInteger & rhs );

You'll probably just want to write your own internal comparison function (like Java's compareTo) and use that.

I/O

• ostream & operator<<( ostream & out, const BigInteger & value);
• istream & operator>>( istream & in, BigInteger & value);

Testing

Create a set of test programs named test1.cpp, test2.cpp, and so forth that demonstrate that the above methods work.

Factorial

Finally, create a program called factorial.cpp that prompts a user for a number and then prints out the factorial of that number. Be sure to only allow the user to input a non-negative value.

Just in case it is useful, 1000! is:

40238726007709377354370243392300398571937486421071463254379991042993851239862902
05920442084869694048004799886101971960586316668729948085589013238296699445909974
24504087073759918823627727188732519779505950995276120874975462497043601418278094
64649629105639388743788648733711918104582578364784997701247663288983595573543251
31853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308
43139284440328123155861103697680135730421616874760967587134831202547858932076716
91324484262361314125087802080002616831510273418279777047846358681701643650241536
91398281264810213092761244896359928705114964975419909342221566832572080821333186
11681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277
61926849034352625200015888535147331611702103968175921510907788019393178114194545
25722386554146106289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746222899880051954
44414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012
54583271682264580665267699586526822728070757813918581788896522081643483448259932
66043367660176999612831860788386150279465955131156552036093988180612138558600301
43569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901
88601856652648506179970235619389701786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886426148396573822911231250241866493
53143970137428531926649875337218940694281434118520158014123344828015051399694290
15348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510640182154399457
15680594187274899809425474217358240106367740459574178516082923013535808184009699
63725242305608559037006242712434169090041536901059339838357779394109700277534720
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000

Keep your memory clean and tidy

To keep you thinking about your memory management, I want you to clean up all memory that you dynamically allocated before the end of the program. That means that you should be able to run under valgrind with no memory leaks reported.

You may need to create destructors for your class as well.

Programming order

1. Start with the constructors, then move on to print and output (so you can test them)
2. Then work on input
3. Then you can branch out to either math operators (start with addition) or relational operators. For the math operators, do the assignment version first (+=) and then use that in the external operator.
4. Once the math is working, you should be able to do factorial pretty easily.

Math help

Some useful tidbits about the math you'll need to do.

Addition

Look back at Homework 5 for details. Recall that in paper and pencil addition, you start by adding together the least significant digits and then calculating if you need a carry to the next space using modulus 10.

Scalar multiplication

When multiplying a BigInteger by a scalar, you perform similar operations as in addition. You multiply the digit by the scalar, add in any carry, and compute the new digit and the carry with modulus mathematics. At the end, continue adding digits until the carry is 0.

Factorial

Recall that N! is the product 1*2*3*...*N-1*N. This grows very, very fast and you will find that an unsigned long is more than enough to use as input.

handin

README

Create a file called README that contains

1. Your name (and partners name) with a description of the programs
2. A listing of the files with a short one line description of the contents
3. Any known bugs or incomplete functions
4. Any interesting design decisions you'd like to share

Now you should make clean to get rid of your executables and handin your folder containing your source files, Makefile, and README.

    % cd ~/cs241
    % handin -c 241 -a 8 hw8
    % lshand

Grading

Here is what I am looking for in this assignment:

• A working Makefile with your test programs, all, and clean as targets
• A class that handles the above overloaded operations
• Appropriately modular code
• Good comments
• Runs under valgrind with no errors or warnings
• A README with the information requested above. The listing of known bugs is important.

Last Modified: December 08, 2008 - Benjamin A. Kuperman