The classical Chinese version of
Horner’s method:
Technical considerations

Donald B. Wagner
12 January 2017
 Minor revisions, 19 May 2020 , 18 October 2021

Classical Chinese mathematicians and calculators routinely extracted the numerical roots of polynomials by a method which is essentially the same as ‘Horner’s method’ as it is sometimes taught in modern schools and colleges. The first digit of the root is determined, the roots of the equation are reduced by the value of that digit (an operation which amounts to a change of variable), the next digit is determined, and this step is repeated until the desired precision is reached. The operation is carried out on paper in the Western version, in the Chinese version with calculating rods laid out on a table.

In this article I shall describe the algorithm in technical detail. A correspondent challenged me here, asking whether it is really possible to use the method without knowing the result beforehand. The answer turns out to be yes, but with some complications.

Historians dealing with early mathematical texts normally express their understanding of a text using equations in modern notation. This provides a clear and precise aid to readers. In this article I have gone a step further: I express the classical Chinese algorithms using computer programs written in the Basic programming language. I would never recommend Basic for serious programming. However it is so simple that readers who have learned programming in any language will understand the programs given here.

In Appendix 1 I have collected a large sample of the polynomials solved in Chinese texts from the 7th to the 14th century. It will be seen that some of the earlier books include only certain classes of polynomials, while the later ones appear to be unlimited in the degree of the polynomial or the use of positive and negative coefficients. The earliest, Wang Xiaotong’s Continuation of ancient mathematics, includes a restricted class of polynomials, making the algorithm for their numerical solution fairly simple. An algorithm for this class will be considered first here.

Jigu suanjing 緝古算經, by Wang
Xiaotong 王孝通, 7th century CE

The title of Wang Xiaotong’s book can be somewhat loosely translated as The continuation of ancient mathematics. He presented it to the Emperor in or about 628 CE. It includes 19 problems in solid or plane geometry which require the numerical solution of one or more polynomials. These are 25 cubics and two quadratics. In the following only the cubics will be considered – the quadratics can be solved by a slight modification of the algorithm for cubics.

Wang Xiaotong’s cubics all have the form

x³ + ax² +bx = c                                                            (1)
a, b ≥ 0, c > 0

Reducing the roots of (1) by a value d gives a new equation,

y³ + (a+3d) y³ + (b+3d²+2ad) y = c–bd–ad²–d³        (2)

where y = x–d. The operation is continued with further digits until c is zero or very small (less than some predetermined ε). Chinese books call this operation chu 除 (‘remove’), and this word is used pars pro toto for the whole operation of extracting roots.

The quantities on the counting board can be seen as variables in a computer program, and an efficient algorithm for obtaining (2) from (1) can be expressed in a computer programming language:

a = a+d                add d to a
b = b+da              add da to b
c = c–db               subtract db from c                           (3)
a = a+d                add d to a
b = b+da              add da to b
a = a+d                add d to a

This algorithm includes only three multiplications, each by a single digit followed by zeroes.

Practical calculators were undoubtedly experienced in guessing the next digit in the root, and were seldom mistaken, but there is a method for finding the next digit without the benefit of experience. First, note that if d is too large, c will become negative at the third line of (3). When the calculator discovers this, he can undo the calculations he has just done, reduce d by 1, and try again. Furthermore, it can be seen from (1) that the positive root must be less than . This can easily be estimated, and a d chosen which is sure to be greater than or equal to the correct digit.

These considerations are brought together in the Basic program shown in Appendix 2. It can find the positive root of any equation of the form (1).

A remaining problem is that several equations in the Jigu suanjing include fractions in the coefficients. How were these dealt with? In some, the denominators of the fractions are divisors of powers of ten, and these are unproblematic. For example, in Problem 17,

x³ + 2³/₄ x² + 2²¹/₅₀ x = 812,591⁵⁹/₁₂₅

the fractions can be rewritten as decimals,

x³ + 2.75x² + 2.42x = 812,591.472

and this gives no problems on the counting board. There are a few equations, however, which are not so easily handled, for example in Problem 11:

x³ + 17 ³⁷/₈₉ x² + 99 ¹⁴/₈₉ x = 6,429 ²⁷/₈₉                                (4)

It turns out that there is a fairly simple method of dealing with such equations on the counting board. First, a common multiple D of the numerators is determined; in this case D = 89. Then the coefficients are converted to improper fractions in which the denominator of a is D, the denominator of b is D², and the denominator of c is D³:

Then the denominators are discarded and the resulting equation is solved by the method given above,

x³ + 1,550x² + 784,193x = 45,322,445,728 

The root found, 1157, is then divided by D to obtain the positive root of (4), x = 13. This procedure amounts to a change of variable, y = Dx.

Appendix 3 gives a Basic program to solve cubic equations in which fractions are treated as described here.

The general case

In later texts the class of polynomials treated is much wider, and especially in Zhu Shijie’s Siyuan yujian (1303 CE) they appear to be perfectly general, with arbitrary degree and with both positive and negative coefficients. These have the general form

and the algorithm to reduce the roots of a polynomial of this form by the value of the next digit, d, corresponding to (3) above, may be written in Basic,

This is simple enough to do on the counting board, but choosing the digit d is no longer as simple as with Wang Xiaotong cubics. In that case it was possible to estimate an upper bound for the one root and work down from there to the correct digit. In the general case there appears to be no easy way for a pre-modern calculator to estimate an upper bound for roots and, in addition, the largest root may not be the one he is looking for. So the calculator must be able to start with a rough estimate of the desired root.

The calculator’s next problem is to determine, after the roots have been reduced by d using (5), whether d is too large or small. In the Basic program given in Appendix 4 the following procedure is used. The program asks for a value of d which is known to be larger that the first digit of the desired root, but less than any higher root. It reduces the roots by this value and stores the sign of the constant coefficient, a₀. From then on, if reduction by d does not result in the sign of a₀ being different from the stored sign, d is too large. A procedure analogous to that for Wang Xiaotong cubics is followed, finding digits until |a₀| is less than some predetermined ε.

The program in Appendix 4 is not a complete solution to the problem. If a polynomial has two roots with the same first digit and the same order of magnitude, it will fail to find either root. There is one case of this in Appendix 1: Siyuan yujian has the equation

          x⁴ – 26x³ – 467x² + 8300x + 97440 = 0

whose roots are 24 and 26.8323. Given this equation as input, the program reports incorrectly that it has no positive real roots. This does not mean that a human calculator could not find these roots. It means only that I am not a good enough programmer.

Estimating the fractional part of the root

It can be seen in Appendix 1 that in one book, Qin Jiushao’s Shushu jiuzhang 數書九章, some roots of polynomials are given with a fractional part. For example, the book gives the root of the polynomial x² + 82,655x – 2,269,810,000 = 0 as 21,742^10,426/_126,140 = 21,742.082654; the correct root is 21,742.082655, so this is a very good approximation. Libbrecht (1973: 198) explains that Qin Jiushao’s approximation is:
if 0 < x < 1 and

         

then

          

I can add that this approximation is equivalent to assuming that f is approximately linear in the interval (0,1),

           

so that

           

It is possible to construct polynomial equations for which Qin Jiushao’s approximation is not good, for example by making p_n very large, but in the cases treated in Shushu jiuzhang it is quite a good approximation.

References