Makefile, bigint.h, bigint.cc, sequence.h, sequence.cc, seqiterator.h, seqiterator.cc, fact.cc, useseq.cc, expo.cc.
You should create a directory cps100 in which all work for this class will be done (see the initial Unix/Emacs/C++ writeup). Each assignment should be done in its own subdirectory, for this assignment create a directory bigint. All work for your assignment will then be done in the directory ~/cps100/bigint.
You should copy the files for this assignment into your bigint directory. To do this, cd into the bigint directory you created and type cp ~ola/cps100/bigint/* . (don't forgot the final .).
For the second part of Part I you must re-implement multiplication of BigInt values. In the implementation you are given, multiplication is performed by repeated addition. You are to fix this so that the grade-school method of multiplying is used as outlined in Section .
Compiling/Running/Explaining Run the program with an input of 2, so that 1! and 2! are computed. You must then explain how/why each diagnostic line of output is generated. Note that to compute there are five calls of the copy constructor and three calls of the assignment operator.
For this part of the assignment you need only submit a writeup that explains why each line is printed. You can save the output in a file by typing
fact 2 > fact2.out
which will save the output in the file named fact2.out. Only two
lines of output will be stored in this file, however, since most of the
diagnostic output is printed to the stream cerr (standard error)
rather than cout (standard out). To capture all output in a file,
run it using
fact 2 >& fact2.out
where the redirection symbol >& captures both standard error and
standard out in the specified file. If the system responds that the
file already exists, you can use
verb
fact 2 >& ! fact2.out
where the bang (exclamation mark) indicates that the file should be
overwritten.
After you have run the program, you'll want to remove the debugging statements. To do this you'll need to edit the Makefile. Remove the -DDEBUG from the line in the Makefile reproduced below.
CFLAGS = -g -DDEBUG
You'll then need to remove bigint.o and recompile. After doing
this, run the program so that it computes all factorials from 40 downto
1. Submit this run with your explanation of the
constructors/destructors.
You should also compile and run the program expo. Use it to compute the value of 3^20 (3486784401). The function Expo2 uses only 7 multiplications whereas Expo uses 20. Yet Expo2 takes much longer. In your README file you should explain why this is the case. As a hint, look carefully at how operator *= is implemented.
A useful first step is to implement a function to multiply a BigInt by an int. To do this properly you will need three functions.
BigInt & operator *= (int num);
BigInt operator * (const BigInt & b1, int num)
BigInt operator * (int num, const BigInt & b1)
The first of these does most of the work, operator * is implemented in
terms of operator *=. The code is very similar to the code for adding
two BigInts (see operator +=). Think about how you would multiply a 50
digit number by the integer 8 using standard ``grade-school'' methods
and translate this into code. You can then add this operator to the
definitions for the class BigInt in the header file bigint.h and
implement it in the .cc file. You'll want to test this code, the
factorial function will do this since it computes the factorial of an
int not a BigInt. You may want to add some diagnostic output when
developing the code to assist in debugging.
1 2 3 4 5 6
x 4 8 9
------------
1 1 1 1 1 0 4
9 8 7 6 4 8 0
8 6 4 1 9 2 0 0
-----------------
9 7 4 0 6 7 8 4
Note that each partial product is shifted-left (padded with the
appropriate number of zeros). Rather than shift the partial product by
adding the appropriate number of zeros, one of the numbers being
multiplied can be shifted (of course this is what is really happening in
the example above where the top number is multiplied by 9, 80, and 700).
This allows the product to be accumulated by summing a sequence of
partial products where each partial product involves multiplying by a
digit in the range 0--9. In the example above the final product is
computed by
(123,456 x 9) + (1,234,560 x 8) + (12,345,600 x 7)
Note that each partial product involves the product of a bigint and a
digit in the range 0-9 (and is thus computable using ther operator with
prototype BigInt & operator *= (int).
You can use the sequence function Prepend to effectively multiply by 10. You need to use Prepend since the least significant digit is stored first. You will do this when writing the operator whose prototype is below.
BigInt & operator *= (const BigInt &);
Note that because BigInt operator *(const BigInt &, const BigInt &)
is implemented in terms of *= you get good performance ``for
free'' for this operator.
For full credit, you should only use Prepend once each time the loop body is executed in the implementation of *=. Read the explanation above carefully to see how this can be done.
submit100 bigint1 README bigint.h bigint.ccIn the README file you should include the annotated output with explanation of why each constructor, destructor, etc. is called. You should also include the output showing all factorials from 40 downto 1. Also include a run of expo.cc that calculates using as describe in the first part of the assignment (with the original BigInt implementation.
You should submit bigint.h and bigint.cc with the multiplication operators implemented as asked for above.
You should also include the output of a run of expo.cc program to calculate to demonstrate your successful implementation of the *= operator for BigInts. If you haven't been successful in implementing you can earn substantial credit for indicating where you think the problems lie in your code. The calculation should be included as part of your README file.
You can submit by typing make submit1 if the correct README file is in the directory from which you submit. You can always edit the Makefile to add or change filenames.
private:
struct Node
{
int digit;
Node * next;
Node(int val, Node * ptr=0) : digit(val), next(ptr){};
};
int mySize;
Node * myFirst; // first node in linked list
Node * myLast; // last node in linked list
In implementing DigitSeq you should use a header node. This means
that an empty sequence will consist of a single node, pointed to by both
myFirst and myLast. Using a header node will simplify writing
several member functions. The default constructor can then be
implemented as shown below (the -1 could be any number).
DigitSeq::DigitSeq()
{
mySize = 0;
myFirst = myLast = new Node(-1); // mark header node
}
The Append and Prepend functions should be no more than
three lines of code each. For example, to append a new digit, a node is
created, myLast is updated to point to it, and mySize is
incremented. Implementing the destructor, copy constructor, and
assignment operator are trickier. For full credit, when implementing
the assignment operator you should make use of nodes that already exist
(e.g., part of the list being assigned to) rather than creating new
nodes unnecessarily.
private:
DigitSeq & mySequence; // bound to this sequence
DigitSeq::Node * myCurrent; // internal index of current item
Note that DigitSeq:: must be used to qualify Node since
Node is declared in the private section of DigitSeq. You should
be careful in implementing the function Current since the pointer
myCurrent may be NULL. It would be wise to check against this,
and if the pointer is NULL, print an error message (to cerr) and
abort the program. Be careful when using myCurrent that you
remember that a header node is used in implementing the
class DigitSeq.
submit100 bigint2 README sequence.h sequence.cc seqiterator.h
seqiterator.cc bigint.h bigint.cc
You can do this by typing make submit2 assuming all files are in
the same directory.
After doing this, you can implement a comparison operator.
bool operator < (const BigInt & a, const BigInt & b)Once this is implemented, all the other relational operators >, <=, >= can be implemented in terms of and . For extra credit, make all these modifications and submit them along with a test program showing that your operators work properly.
Create a README file that discusses your work, your collaborators and your test program. Submit using
submit100 bigintXtra README bigint.h bigint.cc sequence.h sequence.cc ...
Or you can type make submit3 to do this --- you may need to modify
the Makefile depending on how you implement bidirectional iterators.