Most efficient way to compute a polynomial

This seems 5 times faster than the loop y += array_a[index] * Math.Pow(x, index); But I wondering if there is a better way to compute this polynomial? ** For anyone thinks it's a different calculation: I did test the function above. It does the same thing with y += array_a[index] * Math.Pow(x, index); and they compute the same result. Thanks.

@ErwinBolwidt Yes I did. I know it looks like a different calculation. But it does the same thing. You can check.

Is there a better way? It seems like the best way already. Minimal number of computations. Why are you asking? What part don't you like?

@Andreas Yes, I think so. This is the best way but my professor still asked her students to optimize this. So I'm trying to find a better way.

No matter how you fiddle with it, you have to perform n add operations and n+1 multiply operations. That cannot be reduced. By using the a0 + x * (a1 + x*(a2 +. )) formula, you have successfully eliminated the power operations. Well, technically, multiplying by x^0 can be eliminated, so only n multiply operations. Your code is currently doing n+1 adds and multiply's, so you could twiddle it slightly. Note that n = array_a.length - 1 .

1 Answer 1

This is Horner's method. If you only want to calculate it once per polynomial, this is the most efficient algorithm:

… Horner's method requires only n additions and n multiplications, and its storage requirements are only n times the number of bits of x. …

Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal.

If you need to evaluate the polynomial extremely many times and the degree is very high, then there are methods to transform the representation of the polynomial (preconditioning) so that the number of multiplication is reduced to ⌊n/2⌋ + 2. This seems not very practical though, at least I've never seen this in the wild. I've found an online paper that describes some of the algorithms if you are interested.

Also mentioned in the paper, due to the CPU architecture it might be more efficient if you evaluating even and odd terms separately so they can be placed in parallel pipelines:

public double cal(double x) < double x2 = x * x; double y_odd = 0.0, y_even = 0.0; int index = array_a.length - 1; if (index % 2 == 0) < y_even = array_a[index]; index -= 1; >for (; index >= 0; index -= 2) < y_odd = array_a[index] + y_odd * x2; y_even = array_a[index-1] + y_even * x2; >return y_even + y_odd * x; > 

The JIT/compiler might be able to do this conversion for you or even use SIMD to make it very fast automagically. Anyway, for this kind of micro-optimization, always profile before committing to a final solution.