A generalization of Horner's rule for polynomial evaluation

Abstract

A general polynomial of n th degree (1) p(x)=a o +a l x+ ... +a n x n may be evaluated for x = α by use of Horner's rule, i.e., by recursively computing (2) b n = a n b j = a j + αb n+1 j = n-1, ..., 0 from which it follows that (4) p(α) = b o . Horner's rule requires n multiplications and n additions to compute p(α). This is generally accepted as the minimum number of such operations to compute p(α) although no proof exists except for n @@@@ 4.