Efficient Multinomial result

Question

I've got a Multinomial class with private:

unsigned int power;
double *factors;

I'd like to know if there is more efficient way to calculate multinomial's result for given argument?

My current code is:

double Multinomial::calculateFor(double x) const{
    double sum = this->factors[0];
    double prod = 1;
    for(size_t i = 1; i <= this->power; i++){
        prod *= x;
        if(this->factors[i]){
            sum += this->factors[i] * prod;
        }
    }
    return sum;
}

Does the branch cost more than simply unconditionally computing the term? See [Why is processing a sorted array faster than an unsorted array?](http://stackoverflow.com/questions/11227809) for some of the explanation. You should also look up [Horner's Method](http://en.wikipedia.org/wiki/Horner%27s_method) to reduce the number of multiplications. — Jonathan Leffler, Apr 06 '14 at 17:06
@JonathanLeffler Will sorting still be useful if I calculate each multinomial only once? — Michał, Apr 06 '14 at 17:17
How did you arrive at the term "multinomial"? It is the precursor of Stevins (1585) for Vietes (1591) "polynomial", but ever since the early 19th century, the use of "multinomial" is restricted to the discussion of the terms of the expansion of powers of more then two summands like (a+b+c+...+y+z)^n. — Lutz Lehmann, Apr 07 '14 at 16:47
@LutzL English is not my native language, you probably are right, I should have use "polynomial" instead. Thank you. — Michał, Apr 07 '14 at 17:11
The origin of the modern use of "polynomial" is clouded in mystery, until the end of the 19th century they were (entire (rational)) algebraic functions, or numerical functions or functions of some degree. The switch must have happened before 1920, probably before 1910, but may have proceeded in different ways in different languages. The German school system still uses "ganzrationale Funktion". See as another curious (for western ears) example the use of "polygon" as "testing ground" in Slavic languages. — Lutz Lehmann, Apr 07 '14 at 17:28
Thank you for the genesis. I'll keep the difference in mind. — Michał, Apr 07 '14 at 17:38

score 2 · Accepted Answer · edited May 23 '17 at 11:58

I see two ways to speed the computation up.

Conditional branches can slow up computations on modern pipelined processors, so it may be that avoiding the conditional would speed things up. See Why is processing a sorted array faster than an unsorted array? for some of the explanation.
Using Horner's Method saves on the number of multiplications.

Put together, these lead to:

double Multinomial::calculateFor(double x) const
{
    double sum = this->factors[this->power];
    for (size_t i = this->power; i > 0; )
        sum = this->factors[--i] + sum * x;
    return sum;
}

Efficient Multinomial result

1 Answers1