Polynomial multiplication

[geeloso]

I have a class polynomialType that is derived from a base class arrayListType as shown below:

template<class elemType>
class arrayListType
{
      
public:
    const arrayListType<elemType>& operator=(const arrayListType<elemType>&);
    bool isEmpty() const;
    bool isFull() const;
    int listSize() const;          //fn to determine the number of elements in the list
    int maxListSize() const;       //fn to determine the size of the list
    void print() const;
    bool isItemAtEqual(int location, const elemType& item) const;        
    void insertAt(int location, const elemType& insertItem);
    void insertEnd(const elemType& insertItem);
    void removeAt(int location);
    void retrieveAt(int location, elemType& retItem) const;
    void replaceAt(int location, const elemType& repItem);
    void clearList();
    int seqSearch(const elemType& item) const;
    void insert(const elemType& insertItem);
    void remove(const elemType& removeItem);  
    arrayListType(int size = 100);
    arrayListType(const arrayListType<elemType>& otherList);
    ~arrayListType();
    void removeAtBySwap(int location);
    void removeAll(const elemType& removeItem);
    elemType min() const;
    elemType max() const;
    
protected:
    elemType* list;                //array to hold the list elements
    int length;                    //to store the length of the list
    int maxSize;                   //to store the maximum size of the list
};


class polynomialType: public arrayListType<double>
{
    friend ostream& operator<<(ostream&, const polynomialType&);
    friend istream& operator>>(istream&, polynomialType&);
    
public:
    polynomialType operator+(const polynomialType&);
    polynomialType operator-(const polynomialType&);
    polynomialType operator*(const polynomialType&);      //no corresponding member fn definition for this prototype!
    double operator()(double x);         //overloads the operator () to evaluate the polynomial at a given point; the value of
                                         //the polynomial at x is calculated and returned
    polynomialType(int size = 100);
    int min(int x, int y) const;
    int max(int x, int y) const;
};

I wrote a program as shown in function main below to do polynomial multiplications.

int main()
{   
    int sizeA, sizeB;
    
    for (int i = 0; i < 20; i++)
    {
        cout<<"Enter the sizes (degree+1) of the polynomials for multiplication: ";
        cin>>sizeA>>sizeB;
        cout<<endl;
        
        polynomialType p(sizeA);
        polynomialType q(sizeB);
        polynomialType t;
         
        cin>>p;
        cout<<endl<<"p(x) = "<<p<<endl<<endl<<endl;
        
        cin>>q;
        cout<<endl<<"q(x) = "<<q<<endl<<endl<<endl;
            
        t = p * q; 
        
        cout<<"p(x) * q(x) = "<<t<<endl;
        cout<<"=============================================================="<<endl;
        cout<<endl<<endl;
    }
    
    // wait until user is ready before terminating program
    system("PAUSE");
    return 0;
}//end main  

I observed that a single run (without the for loop) of the program to multiply any pair of polynomials works perfectly fine; however, when I iteratively multiply several pairs of polynomials, the multiplication operations are done until an arbitrary point when, on entering the values for sizeA and sizeB, my display screen just disappears!!


Does anyone know what is going on please?!

[TheKingOfTyrants]

Are you saying on the first iteration of the for-loop the program crashes after you enter sizeA and sizeB? Or are you allowed to multiply some pairs before it finally crashes?

[tcs]

It's difficult to answer your question without having a look on your implementation. Maybe there's a bug in dynamic memory allocation or deallocation, or ...

[geeloso]

@Keene:
Definitely not on the first iteration. There is no pattern/order to when the program crashes after the first iteration! It could be after entering sizeA and sizeB for the second pair of polynomials or after multiple entries of such pairs; like I implied in my OP.

@tcs:
I didn't want to obscure the specific problem I'm experiencing with scores of code lines; that's why I intentionally omitted including them. Which of the member functions' implementations would you like to see?

[tcs]

When interpreting a disappearing display screen as a crash of your process, then on my experience this in most cases was caused by a memory access error. This could be a heap allocation or deallocation error. Or there could be an index error usually when writing to an array. So depending on your implementation there could be an error on object creation, destruction or assignment or at least in operator*() implementation or its dependent. I think the output operator<<() and all const methods will not produce any failure. So it may help to have a look at those non-const methods.

[geeloso]

OK. Shown below are implementations for the derived class's constructor, the base class's constructor, operator*() function, operator>>() function, and operator<<() function:

polynomialType::polynomialType(int size):arrayListType<double>(size)      
{
    length = size;        
    
    for (int i = 0; i < size; i++)      
        list[i] = 0;
}   



template<class elemType>    //fn is of O(1)
arrayListType<elemType>::arrayListType(int size)
{
    if (size < 0)
    {
        cerr<<"The array size must be positive. Creating an array of size 100."<<endl;
        maxSize = 100;
    }
    else
        maxSize = size;
        
    length = 0;
    list = new elemType[maxSize];
    assert(list != NULL);
}



polynomialType polynomialType::operator*(const polynomialType& right)
{
    int j, k;   
    int size = length + right.length - 1;  
    polynomialType temp(size);       
        
    for (k = 0; k < size; k++)
    {
        temp.list[k] = 0;           
        for (j = 0; j <= k; j++)
        {        
            if (j >= length)        
                list[j] = 0;           
                
            if ((k-j) >= right.length) 
                right.list[k-j] = 0;   
                
            temp.list[k] = temp.list[k] + list[j] * right.list[k-j];      
        }
    }
            
    return temp;
}



istream& operator>>(istream& is, polynomialType& p)
{
    cout<<"The degree of this polynomial is: "<<p.length - 1<<endl;
    
    for (int i = 0; i < p.length; i++)
    {
        cout<<"Enter the coefficient of x^"<<i<<": ";
        is>>p.list[i];
    }
    
    return is;
}



ostream& operator<<(ostream& os, const polynomialType& p)
{
    int indexFirstNonzeroCoeff = 0;
    
    for (int i = 0; i < p.length; i++)       
        if (p.list[i] != 0.0)
        {
            indexFirstNonzeroCoeff = i;
            break;
        }
    
    if (indexFirstNonzeroCoeff < p.length)   
    {
        if (indexFirstNonzeroCoeff == 0)            
            os<<p.list[indexFirstNonzeroCoeff]<<" ";      
        else                                              
            os<<p.list[indexFirstNonzeroCoeff]<<"x^"<<indexFirstNonzeroCoeff<<" ";
        
        for (int i = indexFirstNonzeroCoeff + 1; i < p.length; i++)
        {
            if (p.list[i] != 0.0)
                if (p.list[i] >= 0.0)      
                    os<<"+ "<<p.list[i]<<"x^"<<i<<" ";
                else
                    os<<"- "<<-p.list[i]<<"x^"<<i<<" ";
        }
    }
    else
       os<<"0";         
        
    return os;
}

Do you spot anything wrong with any of these??

[tcs]

Ok, let us see:

Line 5: size could be less than 0. So better take maxSize as loop termination condition and as value of length.

Line 32: size may result in negative values. ==> See above Line 5.

Line 41, 44, 46: j and (k-j) may become greater than maxSize or right.maxSize. ==> Memory access violation when assigning values to non-existing elements of list or right.list.


Some tips:

1. It is not the best idea to allow others direct uncontrolled access to modify attributes of arrayListType<elemType>. The main purpose of such a class is to ensure consistency of its attribute set. Say f.e. maxSize should reflect the real size of the array or length should ever be less or equal than maxSize. (If having length of type unsigned int it could never become less than 0) In your example derived classes may corrupt their superclass.

2. Overwrite arrayListType<elemType>::operator[] to allow restricted access to array elements. You may want to allow this operator to conditionally increase list memory if the given index is greater or equal than maxSize.

[geeloso]

I'm sorry for the rather long hiatus! Let me just address some of the issues you raised.

Line 5: since size reflects the degree of a polynomial, it can never be negative.

Line 32: same reason as noted above.

Lines 41, 44, 46: j and (k-j) can never be greater than maxSize or right.maxSize; their respective loop condition statements would not allow this scenario to occur!! I however agree with your observation on the

memory access violation

issue.

About the tips!

1. I do not see how I allowed

uncontrolled access

to the data members of the base class since they are protected; only the member functions of a derived class have access to them. Objects of the derived class in function main() cannot still directly access these. How is my derived class corrupting the base class??

2. Your concept of conditionally expanding list depending on the given index is refreshing though!

[tcs]

I'm sorry, but an int parameter in fact can be given a negative value. You may currently think not to give your constructor any negative size but try two polynomials with maxSize being zero. Then have a look at line 32 and you'll see how a negative size parameter may be realized. I didn't say your process may crash due to negative sizes given. But you'll get an array of uninitialized elements in list. For another example see below.

And another sorry, but j and (k - j) in fact may get values greater than maxSize or right.maxSize. Think f.e. about length values of your polynomials closed to their maxSizes.

You may currently know how to leave attributes of a base class you've designed in a consistent state. But in general its not the best idea to even let a derived class object allow manipulating attributes of its superclasses uncontrolled. And in fact you even don't leave your superclass' attributes in a consistent state! Giving a polynomial a negative size parameter value (and this may happen as I've shown), you'll overwrite the superclass length attribute with it. Now your superclass isn't in a consistent state any longer!
As a consequence you should ever declare attributes private and give only controlled modification access by setters or other kind of methods.