Paranthesization of polynomial evaluation
A polynomial of degree N-1 will have N terms (including the constant). And a product of two polynomials each of degree N-1 will have a degree of 2N-2 with 2N-1 terms.
Evaluation of a polynomial function without using any extra storage and extra multiplications can be done using Homer’s rule: by alternatinv addition and multiplication operations appropriately.
p(x) = x^4 + 3x^3 – 6x^2 + 2x + 1 can be paranthesized properly.
A degree of N-1 polynomial evaluation can be paranthesized using N multiplications and N additions. The paranthesization for the above polynomial is
p(x) = x(x(x(x + 3) -6) + 2)) + 1
Assume the coefficients are stored in array representation
for i=0 --> N
y = x * y + Array[i]
If the polynomial is to be evaluated at M different points, then Homers rule woule need M(N-1) multiplications, while by using some extra space we can improve its performance.
However if the polynomial contains only one term x^n, then Homer’s method will degenrate the performance into N-1 multiplications, while it can be done in log(N) steps.
A polynomial of degree N-1 is completely determined by N points. Legranges interpolation formula.
But it can be determined with only 2 points. (the two points being 1 and P(1)+1)
Multiplication of two polynomials of order N can be divided into multiplication of N/2 ordered polynomials and addition.
T(N)