CODEWITHSUNDEEP
algorithmpolynomial-math
Cris Stringfellow
Cris Stringfellow

Reputation: 3808

Given a coefficient vector and a value, what is the fastest way to evaluate a polynomial?

I remember reading somewhere (maybe someone can help remember where), that there is a method that is the fastest for evaluating a polynomial. Something reminds me that it had something to do with Vietta's formula, or the fact that the 0-power coefficient is the product of the 0-power coefficients of any factors of the polynomial.

I know wikipedia says it's Horner's scheme for evaluating fastest. But I recall that you actually did not have to evaluate in that way at all - it had something with the roots?

All I know for sure is that there was a method for evaluating a polynomial that has gives you a "oh that is clever" kind of feeling when you see it, but it's not too difficult and is kind of obvious.

Anyone kind or smart enough to help me out?

It is something along the lines of "you can evaluate P at x by ... " and then there is a really simple little thing that actually avoid having to do any real additions and multiplications on the order of the polynomial degree.

Upvotes: 2

Views: 1071

Answers (2)

Hooked
Hooked

Reputation: 88118

Are you evaluating the polynomial more than once? Is the polynomial particularly simple? Consider the following polynomial:

f(a) = a^(14)

If we want to reduce the number of multiplications required to evaluate f(a) we can compute the minimal addition chain from addition-chain exponentiation:

((a × a→b) × b→d) × d × d × b

Which shows we can compute the f(a) using only 5 multiplications. For a fixed polynomial with small coefficients this can be signifigant savings. Wikipeida notes:

In practice ... shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

For many real-world cases where f(a) can vary another method may be appropriate, but it's worth noting alternate solutions!

Upvotes: 1

Saeed Amiri
Saeed Amiri

Reputation: 22555

I think you looking for Fast Fourier Transform it's good too see this PowerPoint on FFT. In fact FFT is useful when you want to calculate polynomial value in n different point which is O(n log n) and very faster than Horner algorithm.

FFT works on power of n'th root of unit, and uses relation between them and because of this is very fast when you want to compute n different points value.

Upvotes: 1

Related Questions