Polynomial Evaluation

Revision en1, by vatsal, 2016-07-07 18:47:20

I have read Horner's rule for polynomial evaluation which does the work for O(n) where n is the degree of polynomial. Example: Let's take a polynomial of degree 3 -> 3x^3+ x^2 + 9 We are given many value of 'x' and a coefficient vector like [3,1,0,9] and let's take 'x' take to be 3 then it will be evaluated as 3*3^3 + 3^2 + 9 = 81+9+9 = 99 so the answer will be 99. Let's say we have q queries so Horner's rule will take O(nq). Is there any better algorithm? I have heard about FFT and DFT and I have consulted many resources but all in vain. Can anyone help me to understand it please?

Tags math, fft, advanced math, polynomials

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vatsal 2016-07-07 18:47:20 618 Initial revision (published)