Clark University

This algorithm will find a solution to a polynomial equation in one unknown one digit at a time.
It has been known in China for a long time. The method was used for finding square roots and cube roots
in particular, and for quadratic polynomials in general,
about 2000 years ago as described in *The Nine Chapters on the Mathematical Art (Jiuzhang Suanshu.*
Wang Xiaotong (fl. 625) used it to find roots of cubic polynomials, and later it was extended to solving
higher degree equations and to equations with more than one unknown. See the page *Mathematics in China*
at
http://aleph0.clarku.edu/~djoyce/ma105/china.html
for more details. In the West, it was developed much
later by Horner, so the algorithm is also called “Horner’s method.”

The algorithm is best illustrated by example. We’ll consider two. First, a sample cubic equation, then a fifth degree equation used to find the fifth root of 2.

The constant
here is 13258, so we need to find a cube near it. Now 10^{3} is only 1000, too small, and
20^{3} is only
8000, but closer. And 30^{3} is 27000 which is too big. So, we expect the answer to be
between 20 and
30. When you evaluate
*x*^{3} + 2*x*^{2} + 6*x* – 13258
at *x* = 20, you find it’s negative, but it’s positive at *x* = 30. So
we’re certain the solution is between 20 and 30. That means the first digit will be the 2 in 20.

Begin by writing, in columns here, the coefficients of the various powers of *x.* The large
numbers, like 13258 will be grouped in triples of digits to make it easier to see the computations.
(Putting digits in groups of 3 works well for this algorithm when the polynomial is cubic.)

The following tableau shows the first set of computations. We can interpret this step with the help of modern symbolic algebra to see that it corresponds to settingx^{3}x^{2}x^{1}x^{0}1 2 6 -13 258

We now have the entries.x^{3}x^{2}x^{1}x^{0}1 2 6 -13 258 20 20 440 8 920 __ __ ___ ______ 1 22 446 - 4 338 20 20 840 __ __ ___ 1 42 1286 20 20 __ __ 1 62

This will have a solution less than 10. We need to find the next digit. Will it be 0,1, 2, ..., or 9? You can try various digits. Here's what happens when you tryy^{3}y^{2}y^{1}y^{0}1 62 1286 -4 338

So 5 doesn’t work; it’s too big. So is 4, and so is 3. Buty^{3}y^{2}y^{1}y^{0}1 62 1286 -4 338 5 5 335 8 105 __ __ ____ ______ 1 67 1621 whoops, it’s positive!

We now have the entries.y^{3}y^{2}y^{1}y^{0}1 62 1286 -4 338 2 2 128 2 828 __ __ ____ ______ 1 64 1414 -1 510 2 2 132 __ __ ____ 1 66 1546 2 2 __ __ 1 68

The solution will be less than 1. What digit do we guess? To get a guess for the next digit, divide 1546, the coefficient of z, into 1510, the constant, to get about .9. As you can see, .9 will work.z^{3}z^{2}z^{1}z^{0}1 68 1546 -1 510

We now have the entries.z^{3}z^{2}z^{1}z^{0}1 68 1546 -1 510 .9 .9 61.01 1 446.309 __ ____ _______ _________ 1 68.9 1607.01 -55.691 .9 .9 62.82 __ ____ _______ 1 69.8 1669.83 .9 .9 __ ____ 1 78.7

The solution to this equation is now less than 0.1. In fact, it’s pretty close to 55.691/1669.83, about 0.033. The reason it should be close to that number is for w less than 1, the higher powers ofw^{3}w^{2}w^{1}w^{0}1 78.7 1669.83 -55.691

Begin by writing, in columns here, the coefficients of the various powers of *x.*

x^{5}x^{4}x^{3}x^{2}x^{1}x^{0}1 0 0 0 0 -2 00000 00000

Now, we know the 5^{th} root of 2 is between 1 and 2, so the the 5^{th} root of
2 00000 00000 lies between 100 and 200, that is to say, the first digit is 1. The
following tableau shows the first set of computations which corresponds to setting *x*
to 100 + *y* and deriving an equation for *y.*

x^{5}x^{4}x^{3}x^{2}x^{1}x^{0}1 0 0 0 0 -2 00000 00000 100 100 10000 1 000 000 1 0000 0000 1 00000 00000 __ ____ ______ _________ ___________ ______________ 1 100 10000 1 000 000 1 0000 0000 -1 00000 00000 100 100 20000 3 000 000 4 0000 0000 __ ____ ______ _________ ___________ 1 200 30000 4 000 000 5 0000 0000 100 100 30000 6 000 000 __ ____ ______ _________ 1 300 60000 10 000 000 100 100 40000 __ ____ ______ 1 400 100000 100 100 __ ____ 1 500

We now have the entries.

y^{5}y^{4}y^{3}y^{2}y^{1}y^{0}1 500 100000 10 000 000 5 0000 0000 -1 00000 00000

This will have a solution less than 100. We need to find its first digit. Will it be 10, 20, ...,
or 90? Divide 500 000000 into 1 00000 00000, and you get 20. Actually, experience shows it’s
going to be less than 20, so let’s try 10. The following tableau shows the next set of
computations which corresponds to setting *y* to 10 + *z* and deriving an
equation for *z.*

y^{5}y^{4}y^{3}y^{2}y^{1}y^{0}1 500 100000 10 000 000 5 0000 0000 -1 00000 00000 10 10 5100 1 051 000 1 1051 0000 61051 00000 __ ____ ______ _________ ___________ ______________ 1 510 105100 11 051 000 6 1051 0000 -38949 00000 10 10 5200 1 103 000 1 2154 0000 __ ____ ______ _________ ___________ 1 520 110300 12 154 000 7 3205 0000 10 10 5300 1 156 000 __ ____ ______ _________ 1 530 115600 13 310 000 10 10 5400 __ ____ ______ 1 540 121000 10 10 __ ____ 1 550

We now have the entries.

z^{5}z^{4}z^{3}z^{2}z^{1}z^{0}1 550 121000 13 310 000 7 3205 0000 -38949 00000

The solution will be less than 10. What digit do we guess? Divide 732050000 into 389490000 to get about 5. So let’ try 5.

z^{5}z^{4}z^{3}z^{2}z^{1}z^{0}1 550 121000 13 310 000 7 3205 0000 -38949 00000 5 5 2775 618 875 6959 4375 40082 71875 __ ____ ______ _________ ___________ ______________ 1 555 123775 13 918 875 8 0165 4375 whoops, it’s positive!

So 5 was too big. Let’s try 4 instead.

z^{5}z^{4}z^{3}z^{2}z^{1}z^{0}1 550 121000 13 310 000 7 3205 0000 -38949 00000 4 4 2116 492 464 5520 9856 31490 39424 __ ____ ______ _________ ___________ ______________ 1 554 123116 13 802 464 7 8725 9856 -7458 60576 4 4 2232 501 392 5721 5424 __ ____ ______ _________ ___________ 1 558 125348 14 303 856 8 4447 5280 4 4 2248 510 384 __ ____ ______ _________ 1 562 127596 14 814 240 4 4 2264 __ ____ ______ 1 566 129860 4 4 __ ____ 1 570

We now have the entries.

w^{5}w^{4}w^{3}w^{2}1 570 129860 14 814 240 8 4447 5280 -7458 60576

The solution to this equation is now less than one. In fact, it’s pretty close to 745860576 /
844475280 = 0.88322. The reason it should be close to that number is for *w* less than 1, the
higher powers of *w* are pretty small, so they won’t contriubute too much. So, probably the
first digit or two is correct. So
we get, as the 5^{th} root of 2 the number 1.1488. Actually, it’s closer to 1.14869835.

This is a pretty nice algorithm. It’s fairly tedius, but a lot better than guessing.

The Chinese algorithm is pretty much the same thing as the bisection algorithm, but the interval is divided into ten parts instead of into two parts. For human computation, division into ten parts is better, but for computers, division into two parts is slightly faster.

There are yet other algorithms to find roots of functions and solve equations. The bisection method works fine for any continuous functions, but for most of them, the differentiable functions, Newton’s method, which relies on calculus, is significantly faster.

1999, 2002, 2004