(effectively) storing a polynomial dynamically

Question

What i am trying to accomplish is to store an unknown size of a polynomial using arrays. What i have seen over the internet is using an array that each cell contains the coeffecient and the degree is the cell number, but that is not effecient because what if we have a polynomial like : 6x^14+x+5. this would mean we would have zeros all throughout the cells from 1 till 13.Ive already looked at some solutions with vectors and linked lists but is there any other way to effectively tackle this problem, without the use of (std::vectors or std::list)?

Answer 1

Unless there is a compelling reason to act otherwise (this is a programming assignment where you are required to use C-style arrays), you should use a std::vector from the standard library. Libraries are there for a reason: to make your life easier. The overhead is probably insignificant in the context of your program.

You mention that storing a polynomial (such as 4*x^5 + x - 1) in an std::vector with the indices representing the power (such as [-1, 1, 0, 0, 0, 4]) is inefficient. This is true, but unless you are storing polynomials of degree greater than 1000, this waste is entirely insignificant. For "sparse" polynomials, of high degree but with few coefficients, you could consider using a vector of pairs, with the first value of each pair storing the power and the second value storing the coefficient.

Answer 2

A sparse polynomial can be represented with a map, where a zero element is represented by nonexistent key. Here is an example of such class:

#include <map>

//example of sparse integer polynomial
class SparsePolynomial{
    std::map<int,int> coeff;
    int& operator[](const int& degree);
    int get(int degree);
    void update(int degree, int val);
};

Whenever you try to get or update the coefficient of an element, its existence in the map is evaluated. Everytime the coefficient of an element is updated, it is checked whether the value is zero. Hence, the size of the map can always be minimal.

We can replace these two methods with operator[]. However, in that case, we would not be able to check for zero during an update operation, thus the storage would not be as efficient as using two separate methods for access and update.

int SparsePolynomial::get(int degree){
    if (coeff.find(degree) == coeff.end()){
        return 0;
    }else{
        return coeff[degree];
    }
}

void SparsePolynomial::update(int degree, int val){
    if (val == 0){
        std::map<int,int>::iterator it = coeff.find(degree);
        if (it!=coeff.end()){
            coeff.erase(it);
        }
    }else{
        coeff[degree]=val;
    }
}

While this method gives us a more efficient storage, it requires more time for access and update than vector does. However, in the case of a sparse polynomial, the difference can be small. Given a std::map of size N, the average search complexity of an element is O(log N). Suppose you have a sparse polynomial with degree d and number of non-zero coefficients N. If N is much smaller than d, then the access and update time would be small enough not to notice.