The objective of this assignment is to practice writing C++ classes which use exceptions and inheritance/polymorphism.
We want to write a set of classes which will model the behavior of different types of mathematical objects. In this assignment we focus on classes of mathematical objects for which there is a division algorithm which produces a quotient and a remainder. The objects also have a defined integral norm, or size, and the division algorithm is such that the norm of the remainder is always smaller than the norm of the divisor. Such classes of objects are called Euclidean domains. In this assignment we will implement two types of Euclidean domains: polynomials and Gaussian integers (each is described below). Each class will adhere to a common interface, which will be specified in the common base class Euclidean.
Polynomials
Polynomials are functions of the form:
anxn + an-1xn-1 + ... + a1x + a0
where a0, a1, ... , an are any real numbers. The value n is the degree of the polynomial.
The norm of a polynomial is simply its degree.
Polynomials can be added, subtracted, and multiplied in the usual algebraic fashion.
Examples:
(2x2 + 3.2x + 4) + (x3 + 4x2 + 5x + 2.5) = x3 + 6x2 + 8.2x + 6.5
(3x + 4) (x2 + 2x + 3) = (3x3 + 6x2 + 9x) + (4x2 + 8x + 12)
= 3x3 + 10x2 + 17x + 12
Polynomials can also be divided to produce a quotient and a remainder. This algorithm is very similar to the way we divide ordinary integers.
Example:
To divide 4x3 + 7x2 + 2x + 5 by 2x2 + 3x + 6
2x + 0.5
2x2 + 3x + 6 | 4x3 + 7x2 + 2x + 5
(-) 4x3 + 6x2 + 12x
x2 - 10x + 5
(-) x2 + 1.5x + 3
-11.5x + 2
We stop when what's left is of smaller norm (degree) than the divisor. So our quotient is 2x + 0.5, and our remainder is -11.5x + 2.
Gaussian Integers
A Gaussian Integer is a complex number of the form a + bi where and a and b are integers (as opposed to arbitrary real numbers), and i is the "imaginary" square root of -1. Typically, a is called the real part and b is called the imaginary part.
The norm of a Gaussian Integer is given by the formula a2 + b2. (For normal complex numbers the square root is taken, but not here, since Euclidean norms must be integers.)
Gaussian Integers can be added, subtracted and multiplied just as regular complex numbers.
Examples:
(2.1 + 3.5i) + (3 + 6i) = 5.1 + 9.5i
(2 + 3i) (0.5 + 1.5i) = (1 + 3i) + (1.5i + 4.5(i2))
= (1 + 3i) + (-4.5 + 1.5i) = -3.5 + 4.5i
Gaussian Integers can also be divided to produce a quotient and a remainder. To understand this, we first consider the division formula for normal complex numbers:
D = (a + bi) / (c + di) = DR + DIi
where DR = (ac + bd) / (c2 + d2) and DI = (bc - ad) / (c2 + d2)
Note that the two values DR and DI are, in general, non-integral, even for Gaussian integers. When dividing Gaussian integers, the quotient Q is given by:
QR + QIi, where QR is the closest integer to DR and QI is the closest integer to DI
(Remember that in C/C++, converting from a floating-point to an integer gives the next lowest integer, not the closest integer.) The remainder is then computed as any remainder would be:
R = (a + bi) - (c + di)*Q
where the multiplication and subtraction operations are as normally defined for complex.
Example:
To divide 4 + 5i by 2 + 3i, we first compute the actual complex quotient D as (8 + 15) / (4 + 9) + [(10 -12) / (4 + 9)]i to obtain (23/13) - (2/13)i. Thus, the quotient Q is 2 + 0i, and the remainder R is (4 + 5i) - (2 + 0i)(2 + 3i) = 0 - i.
You will implement the classes whose definitions are shown below. You may add whatever private members and functions you see fit to any class; you may not change the public section of any class definition in any way (except that you may omit member function parameter names, and you need not include exactly the same comments). We will be linking your compiled code in with our own main function for testing purposes, so you need not submit a main function definition; however, you will probably want to write one for yourself to help with testing your class implementations.
Abstract Base Class
The Euclidean class will be a base class of the three classes described above. It will serve to provide an interface to each of the methods that are implemented by all of those classes. Note that the methods which return Euclideans return by pointer. This is necessary because in actuality, they will return pointers to the appropriate derived types. The objects returned should be created dynamically; it is the responsibility of the caller to see that they are appropriately destroyed.
class Euclidean
{
public:
virtual ~Euclidean
( ) ; // virtual destructor
virtual int norm ( ) const = 0; // returns the norm
virtual Euclidean* add(const Euclidean* rhs) const = 0;
virtual Euclidean* sub(const Euclidean* rhs) const = 0;
virtual Euclidean* multiply(const Euclidean* rhs) const = 0;
virtual Euclidean* divide(const Euclidean* rhs) const = 0; // returns quotient
virtual Euclidean* mod(const Euclidean* rhs) const = 0; // returns remainder
virtual void print ( ) const = 0; // prints out *this in a human-readable format
private:
}
Derived Classes
The Polynomial and GaussInt classes are described here. Note that each one implements the common set of methods specified in the Euclidean base class. Also, note that the methods add, sub, multiply, divide, and mod take pointers to type Euclidean to conform to the interface in the base class. However, since they actually should only be interacting with Euclideans of their own specific derived type, you should use the dynamic_cast and/or typeid operators (discussed in class) to perform a check of the actual derived type at run-time. If the object is not of the correct type, your program should throw an exception.
However, note also that these methods return pointers to the derived class type, rather than pointers to type Euclidean as declared in the base. This is allowed in C++ because a pointer to a derived type can always be converted to a pointer to a base type. When return types of virtual functions in a base and a derived class differ in this fashion, they are said to be covariant return types. Note that the return type in the derived class can be a subclass of the return type in the base class, but not the other way around. Also, the return types do not have to be identical to the classes themselves, as they are in this example.
If the default assignment operator and/or copy constructor will not be sufficient for any of your derived classes, then you must implement one. You may also add any additional constructors of your choosing to any class; however, the constructors listed here must be implemented.
class Polynomial: public Euclidean
{
public:
Polynomial (int
num_coefficients, double coefficients [ ] ); // constructor
// coefficients listed in descending order of exponent
// if num_coefficients is 0, the value of the polynomial is 0
enum { MAX_COEFFICIENTS = 128 }; // maximum number of coefficients allowed
~Polynomial ( ); // destructor
virtual int norm ( ) const ; // returns the norm
virtual Polynomial* add(const Euclidean* rhs) const;
virtual Polynomial* sub(const Euclidean* rhs) const;
virtual Polynomial* multiply(const Euclidean* rhs) const;
virtual Polynomial* divide(const Euclidean* rhs) const; // returns quotient
virtual Polynomial* mod(const Euclidean* rhs) const; // returns remainder
void print ( ) const; // prints to std :: cout
// Format: 10.3 x^4 + 9.873 x^2 + 3.1 x + 82 ; zero coefficients do not print
double GetCoefficient ( int index ) const; // returns the coefficient of x index
};
class GaussInt: public Euclidean
{
public:
GaussInt ( int real = 0, int imaginary = 0); // constructor
~GaussInt ( ); // destructor
virtual int norm ( ) const; // returns the norm
virtual GaussInt* add(const Euclidean* rhs) const;
virtual GaussInt* sub(const Euclidean* rhs) const;
virtual GaussInt* multiply(const Euclidean* rhs) const;
virtual GaussInt* divide(const Euclidean* rhs) const; // returns quotient
virtual GaussInt* mod(const Euclidean* rhs) const; // returns remainder
GaussInt* conjugate ( ) const; // if *this is a + bi, returns a - bi
void print ( ) const; // prints to std :: cout
// Format: 87 - 42 i ; zero parts do no print, so 87 + 0i prints as 87, and 0 - 4i prints as -4i
int GetReal ( ) const; // returns the real part of the GaussInt
int GetImaginary ( ) const; // returns the imaginary part of the GaussInt
private:
};
Exception Classes
These exception classes must be used in the appropriate situations as described
class DivideByZero // This exception should be thrown if any function listed above tries to divide by zero
{
public:
void PrintInfo ( void ) const; // Prints the name of the subclass and function that tried to divide by zero
private:
};
class IncompatibleType // This exception should be thrown if any of the binary functions are called
// on an object whose runtime type is not compatible with the argument's
// run-time type
{
public:
void PrintInfo ( void ) const; // Prints the name of the subclass and function that threw the exception
private:
};
class PolynomialTooLarge // This exception should be thrown from the constructor of the Polynomial
// class if the array passed is too large, or if any of the binary operators
// produce a result which is too large
{
public:
void PrintInfo ( void ) const; // Prints the name of the function that threw the exception
private:
};
The homework portion of this project will be worth 10% of the project grade. For the homework, create a plain text file (end the filename in .txt) which includes the prototypes of any functions you intend to use that are not listed here, the class definitions you intend to use (include private members/functions), and a one- to two-paragraph (approximately) description of how you intend to implement the member functions. You may use pseudocode if you wish. (This file is not intended to be compiled; it is only for you to express the design of your program.) Your homework will be graded both on the merits of your design and on the extent to which you follow that design in the implementation of your program. Remember to submit your homework file by the homework due date. Late homework submissions are not accepted.
You must include the following statement in a comment section of your program:
I have read and I understand the course policy on cheating. By submitting the following program, I am stating that the program was produced by my individual effort.
Turn in your homework file and program files using the UNIX submit utility, by using the following command at the unix prompt:
submit cs202_02 < hw4 | proj4 > filename
where filename is the name of the file you wish to submit. Remember to submit a plain text file for the homework assignment, your C++ source files for the project, and your makefile. After entering this command, you should get a confirmation that submit was successful:
Submitting filename...OK
You can check your submissions by entering the command:
submitls cs202_02 < hw4 | proj4 >
This will show the names of all files you have submitted for this homework or project, along with the size and submission date and time of each.
This project is due by midnight (1 minute after 11:59pm) on Sunday, 28 April 2001. We will use the system clock as the final arbiter of time and date. Projects turned in up to 24 hours late will receive a 10% penalty; projects submitted between 24 and 48 hours late will receive a 25% penalty. Projects will not be accepted past 48 hours after the due date. Late homework submissions are not accepted.