Algorithm 11.3.4 This algorithm computes the value of the real polynomial a [ n

Question

Algorithm 11.3.4

This algorithm computes the value of the real polynomial a[n]x^n +a[n1]x^(n1) +···+a[2]x^2 + a[1]x + a[0] by nesting successive additions and multiplications as indicated in the following parenthesization:

((···((a[n]x + a[n 1])x + a[n 2])x
+ ···+a[2])x +a[1])x +a[0].

At each stage, starting with a[n], the current value of polyval is multiplied by x and the next lower coefficient of the polynomial is added on.]

Input: n [a nonnegative integer] a[0],a[1],a[2],...,a[n] [an array of real numbers], x [a real number]

Algorithm Body:

polyval := a[n]

for i := 1 to n

polyval :=polyval·x + a[ni]

next i
[At this point polyval= a[n]xn + a[n 1]xn1 + ···+a[2]x2 +a[1]x +a[0].]

Output: polyval [a real number]

Trace Algorithm 11.3.4 for the input n = 2, a[0] = 5, a[1]=1, a[2]=2, and x=3.

Explanation / Answer

polyval := a[n]
for i := 1 to n
polyval :=polyval·x + a[ni]
next i
[At this point polyval= a[n]xn + a[n 1]xn1 + ···+a[2]x2 +a[1]x +a[0].]

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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