Horner’s Rule and Binary Exponentiation

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 xⁿ. Polynomials constitute the most important class of functions because they possess a wealth of good properties on the one hand and can be used for approximating other types of functions on the other. The problem of manipulating polynomials efficiently has been important for several centuries; new discoveries were still being made the last 50 years. By far the most important of them was the fast Fourier transform (FFT). The practical importance of this remarkable algorithm, which is based on representing a polynomial by its values at specially chosen points, was such that some people consider it one of the most important algorithmic discoveries of all time. Because of its relative complexity, we do not discuss the FFT algorithm in this book. An interested reader will find a wealth of literature on the subject, including reasonably accessible treatments in such textbooks as [Kle06] and [Cor09].

Horner’s Rule

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. But according to Knuth [KnuII, p. 486], the method was used by Isaac Newton 150 years before Horner. You will appreciate this method much more if you first design an algorithm for the polynomial evalu-ation problem by yourself and investigate its efficiency (see Problems 1 and 2 in this section’s exercises).

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 x as a common factor in the remaining polynomials of diminishing degrees:

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 a₀. Except for its first entry, which is a_n, the second row is filled left to right as follows: the next entry is computed as the x’s value times the last entry in the second row plus the next coefficient from the first row. The final entry computed in this fashion is the value being sought.

EXAMPLE 1       Evaluate p(x) = 2x⁴ − x³ + 3x² + x − 5 at x = 3.

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

ALGORITHM     Horner(P [0..n], x)

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

//Input: An array P [0..n] of coefficients of a polynomial of degree n, // stored from the lowest to the highest and a number x //Output: The value of the polynomial at x

p ← P [n]

for i ← n − 1 downto 0 do p ← x ∗ p + P [i]

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: a_nxⁿ. Just computing this single term by the brute-force algorithm would require n multiplications, whereas Horner’s rule computes, in addition to this term, n − 1 other terms, and it still uses the same number of multiplications! It is not surprising that Horner’s rule is an optimal algorithm for polynomial evaluation without preprocessing the polynomial’s coefficients. But it took scientists 150 years after Horner’s publication to come to the realization that such a question was worth investigating.

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 x₀ turn out to be the coefficients of the quotient of the division of p(x) by x − x₀, and the final result, in addition to being p(x₀), is equal to the remainder of this division. Thus, according to Example 1, the quotient and the remainder of the division of 2x⁴ − x³ + 3x² + x − 5 by x − 3 are 2x³ + 5x² + 18x + 55 and 160, respectively. This division algorithm, known as synthetic division, is more convenient than so-called long division.

Binary Exponentiation

The amazing efficiency of Horner’s rule fades if the method is applied to comput-ing aⁿ, which is the value of xⁿ at x = a. In fact, it degenerates to the brute-force multiplication of a by itself, with wasteful additions of zeros in between. Since computing aⁿ (actually, aⁿ mod m) is an essential operation in several important primality-testing and encryption methods, we consider now two algorithms for computing aⁿ that are based on the representation-change idea. They both exploit the binary representation of exponent n, but one of them processes this binary string left to right, whereas the second does it right to left.

Let

n = b_I . . . b_i . . . b₀

be the bit string representing a positive integer n in the binary number system. This means that the value of n can be computed as the value of the polynomial

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 n to always square the last value of the accumulator and, if the current binary digit is 1, also to multiply it by a. These observations lead to the following left-to-right binary exponentiation method of computing aⁿ.

ALGORITHM     LeftRightBinaryExponentiation(a, b(n))

//Computes aⁿ by the left-to-right binary exponentiation algorithm //Input: A number a and a list b(n) of binary digits b_I , . . . , b₀

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

product ← a

for i ← I − 1 downto 0 do product ← product ∗ product if b_i = 1 product ← product ∗ a

return product

EXAMPLE 2 Compute a¹³ by the left-to-right binary exponentiation algorithm. Here, n = 13 = 1101₂. So we have

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 aⁿ is

(b − 1) ≤ M(n) ≤ 2(b − 1),

where b is the length of the bit string representing the exponent n. Taking into account that b − 1 = log₂ n , we can conclude that the efficiency of the left-to-right binary exponentiation is logarithmic. Thus, this algorithm is in a better efficiency class than the brute-force exponentiation, which always requires n − 1 multiplications.

The right-to-left binary exponentiation uses the same binary polynomial p(2)

(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²ⁱ , skipping those for which the binary digit b_i is zero. In addition, we can compute a²ⁱ by simply squaring the same term we computed for the previous value of i since a²ⁱ = (a²ⁱ⁻¹)². So we compute all such powers of a from the smallest to the largest (from right to left), but we include in the product accumulator only those whose corresponding binary digit is 1. Here is pseudocode of this algorithm.

ALGORITHM                 RightLeftBinaryExponentiation(a, b(n))

//Computes aⁿ by the right-to-left binary exponentiation algorithm //Input: A number a and a list b(n) of binary digits b_I , . . . , b₀

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

t erm ← a //initializes a²ⁱ if b₀ = 1 product ← a

else product ← 1 for i ← 1 to I do

t erm ← t erm ∗ t erm

if b_i = 1 product ← product ∗ t erm return product

EXAMPLE 3 Compute a¹³ by the right-to-left binary exponentiation method. Here, n = 13 = 1101₂. So we have the following table filled in from right to

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], x)

//Computes the value of polynomial P at a given point x //by the “highest to lowest term” brute-force algorithm

//Input: An array P [0..n] of the coefficients of a polynomial of degree n, // stored from the lowest to the highest and a number x

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

for i ← n downto 0 do power ← 1

for j ← 1 to i do

power ← power ∗ x p ← p + P [i] ∗ 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) = 3x⁴ − x³ + 2x + 5                     at x = −2.

            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 x + 2.

           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) = a_nxⁿ + a_n−1xⁿ⁻¹ + ^{. . .} + a₀ by

x − c, where c is some constant, with the number of these operations in the “synthetic division.”

       Q.      a.  Apply the left-to-right binary exponentiation algorithm to compute a¹⁷.

            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¹⁷.

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

       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ⁿ + xⁿ⁻¹ + ^{. . .} +

x + 1?

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

p(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + ^{. . .} + a₀

can be represented in the form

p(x) = a_n(x − x₁)(x − x₂) . . . (x − x_n)

where x₁, x₂, . . . , 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) where no two x_i are the same, find a polynomial p(x) of degree at most n − 1 such that p(x_i) = y_i for every i = 1, 2, . . . , n.