6
\$\begingroup\$

How could I improve this sigma calculator library, so it is easier to use? For example, the polynomial class is clumsy because I am not able to pass just a list of terms to the constructor, I must use the addTerm function instead. Also when passing values to the term constructor it's unclear which argument is the coefficient and which is the exponent, unless you think about it a little.

#include <list>
#include <math.h>
#include <iostream>

class term {
    int coef;
    int exp;
public:
    term(int coef, int exp) : coef(coef), exp(exp) { }
    double substitute(int valForX)
    {
        return coef * pow(valForX, exp);
    }
};
class polynomial {
    std::list<term> poly;
public:
    polynomial() { }
    void addTerm(const term &t)
    {
        poly.push_back(t);
    }
    double substitute(int valForX)
    {
        double sum = 0;
        for (auto it = poly.begin(); it != poly.end(); ++it)
            sum += it->substitute(valForX);

        return sum;
    }
};

double sigma(int start, int end, polynomial rule)
{
    double sum = 0;
    for (int i = start; i <= end; ++i)
        sum += rule.substitute(i);
    return sum;
}
double sigma(int start, int end, term rule)
{
    polynomial p;
    p.addTerm(rule);
    return sigma(start, end, p);
}

Also I feel the performance of the substitute calls are slow, because there are many of them being done.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ How important is accuracy to you? If it plays only a minor role, you could maybe improve the performance of substitute by replacing your calls to pow with simple multiplication while memoizing the intermediate results, i.e. calculate x^2 and use it, then calculate x^3 by simply multiplying with x etc. Of course, this is only beneficial if you have a lot of adjacent powers. \$\endgroup\$ Sep 4, 2017 at 16:12
  • \$\begingroup\$ @BenSteffan I will implement that. I'll do a switch on the coef to select if its one, two, or three. If its bigger than that, then i will call pow \$\endgroup\$
    – stackptr
    Sep 4, 2017 at 16:34
  • 1
    \$\begingroup\$ No, that is not really what I meant. Just calculate adjacent coefficients by multiplying by x. For example, if you have coefficients 46, 47 and 48, calculate 46 by using pow, then calculate 47 by multiplying 46 with x, then calculate 48 by multiplying 47 by x. \$\endgroup\$ Sep 4, 2017 at 16:38
  • \$\begingroup\$ @BenSteffan, adding terms with the same exponent together will make the task very easy! But without it, the approach will require some sort of storage with linear complexity in memory. \$\endgroup\$ Sep 4, 2017 at 16:43
  • \$\begingroup\$ @BenSteffan Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements in answers. \$\endgroup\$ Sep 4, 2017 at 18:25

2 Answers 2

6
\$\begingroup\$

This code is really straightforward and easy to understand. Some thoughts:

Making It Easier To Use

You ask, "How could I improve this sigma calculator library, so it is easier to use?" You talk about the fact that a user of this class will have to call addTerm repeatedly to make use of it. There are a few other options, though it's not clear that they are better.

  1. Write a factory function that uses variadic arguments. It might look something like this:
polynomial* makePolynomial(int count, ...)
{
    polynomial* result = new polynomial;
    
    va_list ap;
    va_start(ap, count);
    for (int i = 0; i < count; i++)
    {
        result->addTerm(va_arg(ap, term));
    }
    va_end(ap);
    
    return result;
}
  1. Have a constructor or factory function that takes a string that you parse. It could be in some format like "c1,e1;c2,e2;" etc. In this case the c variables would be coefficients and the e variables would be exponents. Parsing strings can be error prone, so I tend to dislike this particular solution, but it does make it nice for the caller.

In terms of clarifying which argument to the constructor is the coefficient and which is the exponent, I think you've done what you can. You put them in the order people are used to writing them and have named them appropriately. I don't see anything else you could do unless you want to get ridiculous and make a coefficient type and an exponent type. That seems like overkill for what are int arguments. I wouldn't recommend that.

Improving Performance

To know for sure why it's slow (or even if it's slow) you should profile it and see where the slowdowns occur. I can make an educated guess, but it's just that – a guess. The substitute method in term is doing 2 things that are often a performance problem: 1) (implicitly) casting from int to double, and 2) calling pow().

You can completely remove the casts by making coef and exp be double. You can even leave the constructor as only taking int if you want to limit them to being integer values. But internally, they'd be stored as double to make the calculation faster. This way if you call substitute repeatedly with the same term it doesn't do the conversion multiple times. (If you only call it once, then you haven't improved performance – you've only changed where the slow code happens. Now part of it happens during construction.)

As for pow, since you know that exp is always an integer value, you could instead write a loop. I'd do some experiments to see at which point it's no longer a win because I'm sure looping a thousand times to calculate x^1000 is probably slower than just calling pow(x, 1000.0);

Idiomatic C++

If you're using C++11 or later, I'd change the substitute() method to use the newer ranged loop structures:

for (auto nextTerm : poly)
{
    sum += nextTerm->substitute(valForX);
}
\$\endgroup\$
5
  • \$\begingroup\$ Couldn't I make the variable argument list be in the polynomial constructor itself? \$\endgroup\$
    – stackptr
    Sep 4, 2017 at 16:31
  • 1
    \$\begingroup\$ I haven't done that before. If I recall correctly, you can't do it with normal constructors, only with template constructors. But I could be wrong. I tried looking it up, but all searches only turned up variadic template constructors, unfortunately. \$\endgroup\$ Sep 4, 2017 at 16:32
  • 2
    \$\begingroup\$ @stackptr, variable argument list is a C feature. I strongly advise you to not use it. Something like template parameter pack would be ok, but iterator based and initializer list based solution is a standard one. \$\endgroup\$ Sep 4, 2017 at 16:32
  • \$\begingroup\$ @user1118321, the last one would be std::accumulate call with a lambda. Might be longer, but I believe it might be more readable. \$\endgroup\$ Sep 4, 2017 at 16:38
  • \$\begingroup\$ Yes, that would make sense too! Good call! \$\endgroup\$ Sep 4, 2017 at 18:43
5
\$\begingroup\$

Architecture overview

Well, it started good, but turned bad. Very bad.

First of all, lets kick off from important things

Debunking myths

I am not able to pass just a list of terms to the constructor

This one is especially wrong. One can just have

template <typename InputIterator>
polynomial(InputIterator first, InputIterator last):
                                        poly(first, last)
{}

This will allow constructing the polynomial from any iterator based container.

when passing values to the term constructor it's unclear which argument is the coefficient and which is the exponent,

This is not so relevant these days, but tired programmer can still do a mistake or thousand of them.

Also I feel the performance of the substitute calls are slow, because there are many of them being done.

This is hard to prove, as there are no facts. On the one hand, we have std::pow(), which does all of the precision caring stuff, on the other hand, we have traversal of a linked list.

Possibly better architecture

term class is the correct step. Though everything else after that is just bad abstraction. Lets think about current abstraction:

  • term - encapsulates a term. Has a member function to substitute a value. May be not entirely nitpick proof, but is good already.

  • polynomial - encapsulates a container of terms and provides operation to substitute a value on all of the terms. But why does it take ownership of terms? Why are they bound to std::list which has bad traversing performance? C++ doesn't give performance, it gives control over performance. And now performance is certainly not first class citizen of the code.

Now, after having some ideas about where did it get wrong, lets create a new abstraction:

  • let term be a struct of const ints (for now).

  • Make a function which would substitute a value into term, e.g. a free function.

  • Make iterator based algorithm to perform the substitution on a range of terms. This way people will have ability to choose what their container is, or you can directly substitute from a stream. It is a simple std::accumulate call with a lambda.

  • Transform the sigma function into iterator based function. Do note that due to multipass requirement the function won't be able to do it directly from the stream, but anything slightly stronger and higher like ForwardIterator will do.

Performance

We've dealt with the abstraction, now lets consider performance. What mathematically clean optimizations can we do? (they are going in first as they are easier to reason about in most of the cases)

  1. Add all terms that have the same exponent.

    Now this one will require a standalone polynomial class, probably containing something like std::unordered_map.

  2. Memorize previous powers (as Ben said)

  3. Perform some other trickery I'm unaware of

Then, I believe, the last thing is to look at what compiler made of it, and see if there are things to improve. Do note though, always benchmark, because sometimes ignorance, which we all have to some extent, might play a very bad game with you.

\$\endgroup\$
2
  • \$\begingroup\$ How exactly would this kind of constructor work? template <typename InputIterator> polynomial(InputIterator first, InputIterator last): poly(first, last){} Like this? polynomial poly { range.begin(), range.end() }; \$\endgroup\$
    – stackptr
    Sep 4, 2017 at 16:39
  • \$\begingroup\$ @stackptr, you call it like that, yes. But also polynomial poly{std::istream_iterator<term>{std::cin}, {}}; to extract from a stream or anything else that is single pass. Do not forget to add initializer list constructor, which should just delegate to iterator based one. \$\endgroup\$ Sep 4, 2017 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.