CODEWITHSUNDEEP
algorithmperformancepolynomial-mathcomputation
ZuluForce
ZuluForce

Reputation: 237

Efficient polynomial evaluation with Horner's Algorithm

I have the equation y = 3(x+1)^2 + 5(x+1)^4.

Using Horner's scheme I could evaluate this polynomial in this form, y = 8+x(26+x(33+x(20+5x))), thus requiring 8 arithmetic operations.

I could also evaluate it in this form, y = (x+1)^2 * ((5x+10)x+8), requiring 7 operations.

I've been told this can be done in 5 operations but Horner's algorithm is supposed to be most efficient and it can only do it in 7 operations. Am I missing something?

Upvotes: 2

Views: 1326

Answers (2)

Keith Randall
Keith Randall

Reputation: 23265

3(x+1)^2 + 5(x+1)^4 = (x+1)^2[3 + 5(x+1)^2].

I can do that in 5 operations:

1) x+1
2) (x+1)^2
3) 5(x+1)^2
4) 5(x+1)^2 + 3
5) (x+1)^2[5(x+1)^2 + 3]

Upvotes: 1

Jim Lewis
Jim Lewis

Reputation: 45025

Let a = (x+1)^2, that's 2 ops. Then y=3a + 5a^2 = a(3+5a), 3 more ops for a total of 5.

Upvotes: 6

Related Questions