Horner’s rule is an old but very elegant and efficient algorithm for evaluating a polynomial. It is named after the British mathematician W. G. Horner, who pub-lished it in the early 19th century.

**Horner’s Rule and
Binary Exponentiation**

In this section, we discuss the problem of
computing the value of a polynomial

at a given point ** x** and its important special case of computing

**Horner’s Rule**

** Horner’s rule **is an old but very elegant and efficient
algorithm for evaluating a

Horner’s rule is a good example of the
representation-change technique since it is based on representing ** p(x)** by a formula different from (6.1). This new formula is obtained
from (6.1) by successively taking

It is in formula (6.2) that we will substitute
a value of ** x** at which the polyno-mial needs to be evaluated. It is hard to
believe that this is a way to an efficient algorithm, but the unpleasant
appearance of formula (6.2) is just that, an appear-ance. As we shall see,
there is no need to go explicitly through the transformation leading to it: all
we need is an original list of the polynomial’s coefficients.

The pen-and-pencil calculation can be
conveniently organized with a two-row table. The first row contains the
polynomial’s coefficients (including all the coefficients equal to zero, if
any) listed from the highest ** a_{n}** to the lowest

**EXAMPLE 1** Evaluate
** p(x)** = 2

Pseudocode of this algorithm is the shortest
one imaginable for a nontrivial algorithm:

**ALGORITHM** *Horner**(P** *[0** ..n**]

//Evaluates a polynomial at a given point by
Horner’s rule

//Input: An array ** P** [0

** p **←

**for ***i*** **←** ***n*** **−** **1** downto
**0** do **** p **←

**return ***p*

The number of multiplications and the number of
additions are given by the same sum:

To appreciate how efficient Horner’s rule is,
consider only the first term of a polynomial of degree ** n**:

Horner’s rule also has some useful byproducts.
The intermediate numbers generated by the algorithm in the process of
evaluating ** p(x)** at some point

**Binary Exponentiation**

The amazing efficiency of Horner’s rule fades
if the method is applied to comput-ing ** a^{n}**, which is the value of

Let

** n **=

be the bit string representing a positive
integer ** n** in the binary number system. This means that the value of

Let us now compute the value of this polynomial
by applying Horner’s rule and see what the method’s operations imply for
computing the power

Thus, after initializing the accumulator’s
value to ** a**, we can scan the bit string representing the exponent

**ALGORITHM** *LeftRightBinaryExponentiation**(a**, **b(n))*

//Computes ** a^{n}** by the left-to-right binary exponentiation
algorithm //Input: A number

// in the binary expansion of a positive
integer ** n** //Output: The value of

** product **←

**for ***i*** **←** ***I*** **−** **1** downto
**0** do **** product **←

**return ***product*

**EXAMPLE 2 **Compute** a**

Since the algorithm makes one or two
multiplications on each repetition of its only loop, the total number of
multiplications ** M(n)** made by it in computing

** (b **−

where ** b** is the length of the bit string representing
the exponent

The ** right-to-left binary exponentiation**
uses the same binary polynomial

(see (6.4)) yielding the value of ** n**. But rather than applying Horner’s rule to it as the previous
method did, this one exploits it differently:

i.e., the product of consecutive terms *a*^{2}**^{i}** , skipping those for which the binary digit

**ALGORITHM** *RightLeftBinaryExponentiation**(a**, **b(n))*

//Computes ** a^{n}** by the right-to-left binary exponentiation
algorithm //Input: A number

// in the binary expansion of a nonnegative
integer ** n** //Output: The value of

** t erm **←

**else ***product*** **←** **1** for ***i*** **←** **1** to ***I*** do**

** t erm **←

**if ***b _{i}*

**EXAMPLE 3 **Compute** a**

left:

Obviously, the algorithm’s efficiency is also
logarithmic for the same reason the left-to-right binary multiplication is. The
usefulness of both binary exponentia-tion algorithms is reduced somewhat by
their reliance on availability of the explicit binary expansion of exponent ** n**. Problem 9 in this section’s exercises asks you to design an
algorithm that does not have this shortcoming.

**Exercises 6.5**

Q. ** **Consider the following brute-force algorithm
for evaluating a polynomial.

**ALGORITHM** *BruteForcePolynomialEvaluation**(P** *[0** ..n**]

//Computes the value of polynomial ** P** at a given point

//Input: An array ** P** [0

//Output: The value of the polynomial at the
point *x*** p **←

**for ***i*** **←** ***n*** downto **0** do **** power **←

**for ***j*** **←** **1** to ***i*** do**

** power **←

**return ***p*

Find the total number of multiplications and
the total number of additions made by this algorithm.

** **Q. **
**Write
pseudocode for the brute-force polynomial evaluation that stems from
substituting a given value of the variable into the polynomial’s formula and
evaluating it from the lowest term to the highest one. Determine the number of
multiplications and the number of additions made by this algorithm.

** **Q. **
****a. **Estimate how much faster Horner’s rule is compared to the
“lowest-to-highest term” brute-force algorithm of Problem 2 if (i) the time of
one multiplication is significantly larger than the time of one addition; (ii)
the time of one multiplication is about the same as the time of one addition.

**
**Is
Horner’s rule more time efficient at the expense of being less space efficient
than the brute-force algorithm?

**
****a. **Apply Horner’s rule to evaluate the polynomial

** p(x) **=

**
**Use the
results of the above application of Horner’s rule to find the quo-tient and
remainder of the division of ** p(x)** by

** **Q. Apply
Horner’s rule to convert 110100101 from binary to decimal.

Q. Compare the number of multiplications and additions/subtractions
needed by the “long division” of a polynomial ** p(x)** =

** x **−

** **Q. **
****a. **Apply the left-to-right binary exponentiation
algorithm to compute** ***a*^{17}*.*

**
**Is it
possible to extend the left-to-right binary exponentiation algorithm to work
for every nonnegative integer exponent?

** **b. **
**Apply
the right-to-left binary exponentiation algorithm to compute *a*^{17}*.*

** **Q. **
**Design a
nonrecursive algorithm for computing ** a^{n}** that mimics the right-to-left binary
exponentiation but does not explicitly use the binary representation of

** **Q. **
**Is it a
good idea to use a general-purpose polynomial-evaluation algorithm

such as Horner’s rule to evaluate the
polynomial ** p(x)** =

** x **+

** **Q. **
**According
to the corollary of the Fundamental Theorem of Algebra, every polynomial

** p(x) **=

can be represented in the form

** p(x) **=

where *x*_{1}*, x*_{2}** , . . .
, x_{n}** are the
roots of the polynomial (generally, complex and not necessarily distinct).
Discuss which of the two representations is more convenient for each of the
following operations:

**
**polynomial
evaluation at a given point

**
**addition
of two polynomials

**
**multiplication
of two polynomials

** **Q. **
***Polynomial interpolation *Given a set of* **n** *data points* **(x _{i}, y_{i})*

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Transform and Conquer : Horner’s Rule and Binary Exponentiation |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.