How to evaluate all derivatives of a polynomial at a point with FFT? [closed]
-
31-10-2019 - |
Question
I found this problem:
Evaluating all derivatives of a polynomial at a point
Given a polynomial A(x) of degree-bound n, its tth derivative is defined by
From the coefficient representation $(a_0, a_1, . . . , a_{n-1})$ of A(x) and a given point $x_0$, we wish to determine A(t) ($x_0$) for t = 0, 1, . . . , n - 1.
I know the vector of the coefficients has to be used and I also know that the derivative of a term $ax^n$ is $a*n*x^{n-1}$, but where do I go from there?
I can only think of the naïve scheme to evaluate this: Find the first derivative ($O(n)$), evaluate it using Horner's method ($O(n)$). Repeat this for all deterivaties, giving $(O(n^2)$).
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange