vatsal's blog

Polynomial Evaluation
By vatsal, history, 8 years ago, In English

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?

  • Vote: I like it
  • -20
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Indirectly You are asking for help for a live contest question : https://www.codechef.com/JULY16/problems/POLYEVAL

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What a coincidence, I am solving the same problem on Codechef right now!

→ Reply