c=2

a0=1, a1=1, a2=3

put y=a3=3

first trip

y=c*y+a1=7

second trip

y=c*y+a0=2*7+1=15

Done.

There is 1 multiplication per trip around the loop, and the final trip count is n, so there are n multiplications.Also, how many multiplications are used by this algorithm to evaluate a polynomial of degree n at x = c?

procedure Horner(c, a0, a1, a2, ... , an : real numbers)

y:= an

for i := 1 to n

y := y * c + a (n-i)

{y = an c^n + a(n-1) c^n-1 + ... + a1c + a0}

RonL