A polynomial of degree n is of the form P(x) = anxn + an-1xn-1 + an-2xn-2 + ...

Question

A polynomial of degree n is of the form P(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a1x + a0 where a0, a1,..., an are some constants called the coefficients and x is a variable. Assume that you have two sub-procedures for addition and multiplication. Describe an algorithm that takes as input the coefficients a0, a1, ..., an and value v, and computes the value of P(v). What is the total number of multiplication and additions performed by your algorithm? Can you design an algorithm that only requires O(n) multiplications and additions?

Explanation / Answer

a) ALGORITHM:

compute( a0,a1,.....an,v) :

int res = 0;

for(int i = 0; i <= n; i++ )

res += a[i] * pow(v,i);

return res;

Total number of multiplications = 1 + 2 + 3 + ... n+1 = (n+1)(n+2)/2

additions = n

b) Yes, using an idea similar to FFT we can reduce that.

Divide the coefficients into two arrays and do the following:

res = compute(a0,a1,...an/2,v) + pow(x,n/2)* compute(an/2 +1, an, v)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.