nested multiplication 349

527–43

0 10 85 405

217 81 408

bers, deeming these quantities as “meaningless” and

“absurd.” This attitude generally persisted for the cen-

tury that followed, even though scholars found it neces-

sary to work with them algebraically as they solved

more sophisticated mathematical equations. By the turn

of the 18th century, however, it was generally admitted

that negative numbers are a necessary construct in math-

ematics. L

EONHARD

E

ULER

(1707–83) was comfortable

working with negative quantities.

With the development of

ABSTRACT ALGEBRA

in

the 19th century, the need to assign “meaning” to

numbers became less important. Even though some

19th-century scholars such as A

UGUSTUS

D

E

M

ORGAN

continued to publish commentary against the validity

of negative quantities, their usefulness, and necessity,

was generally accepted.

See also B

ABYLONIAN MATHEMATICS

; C

HINESE

MATHEMATICS

; E

GYPTIAN MATHEMATICS

; G

REEK MATH

-

EMATICS

;

NUMBER

;

POSITIVE

.

nested multiplication To evaluate a

POLYNOMIAL

such as p(x) = 2x3+ 7x2– 4x+ 3 for a particular value

x= 5, say, one simply substitutes 5 for xand performs

the required number of multiplications. In this exam-

ple, 3 + 2 + 1 = 6 multiplications are needed:

p(5) = 2 ×5 ×5 ×5 + 7 ×5 ×5 – 4 ×5 + 3 = 408

(It is generally the case that a polynomial contains a

TRIANGULAR NUMBER

of products.) The number of

multiplications required can be significantly reduced if

one first rewrites the polynomial in a form known as

nested multiplication. In this example we write:

p(x) = 2x3+ 7x2–4x+ 3

= (2x2+ 7x– 4)x+ 3

= ((2x+ 7)x– 4)x+ 3

Thus p(5) can be computed with just three operations

of multiplication:

p(5) = ((2 ×5 + 7) ×5 – 4) ×5 + 3

= ((10 + 7) ×5 – 4) ×5 + 3

= (85 – 4) ×5 + 3

= 408

Notice that this process simply multiplied the first

coefficient by 5, added the second coefficient, multi-

plied the result by 5, added the third coefficient, multi-

plied by 5, and then added the final coefficient. The

process is compactly recorded in a table as follows:

The first row lists the coefficients of the polyno-

mial and a zero is placed under the first coefficient.

One works from left to right adding the entries in the

two rows, multiplying the result by 5, and recording

that result in the next column. The entry in the bottom

right corner is the value p(5).

The remaining numbers on the bottom row have a

surprising interpretation. According to the

FACTOR

THEOREM

, if the polynomial p(x) is divided by the term

x– 5, then the remainder will be p(5) = 408. In this

example one can check that

The numbers on the bottom row of the table above

are precisely the coefficients of the quotient. This

same phenomenon occurs for any polynomial of any

degree. Examining an abstract example illustrates why

this works. (For simplicity we will again work with a

cubic equation.)

Consider the polynomial p(x) = ax3+ bx2+ cx + d

divided by the linear term x– h. The process of

LONG

DIVISION

yields the following:

On the other hand, the method of evaluating p(h) via

the process of nested multiplication yields the table: