Horner’s method:

Technical considerations

Donald B. Wagner

12 January 2017

**On Horner’s method** see e.g. Rees & Sparks 1967: 294–297 as well as numerous pages on the World Wide Web. Horner (1819) presented a procedure for approximating roots of any infinitely differentiable function, but modern descriptions of ‘Horner’s method’ consider only the case of polynomial functions.

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.

Xiaotong 王孝通, 7th century CE

On this book see especially Lim & Wagner (2013a; 2013b; 2017).

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^{3}+ax^{2}+bx=c(1)

a,b≥ 0,c> 0

We define a ‘Wang Xiaotong cubic’ to be a function of the form

* f*(*x*) = *x*^{3} + *ax*^{2} + *bx* – *c*

* a*, *b* ≥ 0, *c* > 0

We shall prove that such a function has exactly one positive real root.

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

y^{3}+ (a+3d)y^{3}+ (b+3d^{2}+2ad)y=c–bd–ad^{2}–d^{2 }(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+dadddtoa

b=b+daadddatob

c=c–dbsubtractdbfromc(3)

a=a+dadddtoa

b=b+daadddatob

a=a+dadddtoa

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^{3}+ 2^{3}/_{4}x^{2}+ 2^{21}/_{50}x= 812,591^{59}/_{125}

the fractions can be rewritten as decimals,

x^{3}+ 2.75x^{2}+ 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^{3}+ 17^{37}/_{89}x^{2}+ 99^{14}/_{89}x= 6,429^{27}/_{89}(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*^{2}, and the denominator of *c* is *D*^{3}:

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

x^{3}+ 1,550x^{2}+ 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.

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,

for m=0 to n–1

for i=n–1 to m step –1

a(i) = a(i) + d*a(i+1) (5)

next i

next m

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*_{0}. From then on, if reduction by *d* does not result in the sign of *a*_{0} 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*_{0}| 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*^{4} – 26*x*^{3} – 467*x*^{2} + 8300*x* + 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.

Chemla, Karine, and Guo Shuchun. 2004. *Les neuf chapitres: Le classique mathématique de la Chine ancienne et ses commentaires*. Paris: Dunod.

Chemla, Karine. 1982. *Étude du livre «Reflets des mesures du cercle sur la mer»*. Unpublished dissertation, University of Paris XIII.

Chemla, Karine. 1994. ‘Similarities between Chinese and Arabic Mathematical Writings: (I) Root extraction’. *Arabic Sciences and Philosophy* 4: 207–266. journals.cambridge.org/abstract_S0957423900001235

Horner, W. G. 1819. ‘A New Method of Solving Numerical Equations of All Orders, by Continuous Approximation’. *Philosophical Transactions of the Royal Society of London* 109: 308–335. www.jstor.org/stable/107508

Lam Lay-Yong [Lan Lirong 蓝丽蓉]. 1970. ‘The geometrical basis of the ancient Chinese square-root method’. *Isis* 61.1: 92–102. www.jstor.org/stable/229151

Lam Lay-Yong [Lan Lirong 蓝丽蓉]. 1977. *A critical study of the Yang Hui Suan Fa, a 13th-century Chinese mathematical treatise*. Singapore: Singapore University Press.

Lam Lay-Yong [Lan Lirong 蓝丽蓉]. 1986. ‘The development of polynomial equations in traditional China’. *Mathematical medley* (Singapore Mathematical Society) 14.1: 9–34.

Libbrecht, Ulrich. 1973. *Chinese mathematics in the thirteenth century: The Shu-shu chiu-chang of Ch’in Chiu-shao*. (MIT East Asian science series, 1). Facs. repr. Mineola, NY: Dover, 2005.

Lim, Tina Su Lyn, and Donald B. Wagner. 2013a. ‘The Grand Astrologer’s platform and ramp: Four problems in solid geometry from Wang Xiaotong’s ‘Continuation of ancient mathematics’ (7th century AD)’. *Historia Mathematica* 40.1: 3–35. www.sciencedirect.com/science/article/pii/S0315086012000596

Lim, Tina Su Lyn, and Donald B. Wagner. 2013b. ‘Wang Xiaotong on right triangles: Six problems from ‘Continuation of ancient mathematics’ (7th century AD)’. *East Asian science, technology and medicine* 37: 12–35. Published 2016. www.eastm.org/index.php/journal/article/view/648/562

Lim, Tina Su Lyn, and Donald B. Wagner. 2017. *The continuation of ancient mathematics: Wang Xiaotong’s Jigu suanjing, algebra and geometry in 7th-century China*. Copenhagen: NIAS Press. Forthcoming.

Martzloff, Jean-Claude. 1997. *A history of Chinese mathematics*. Tr. by Stephen S. Wilson. Berlin / Heidelberg: Springer-Verlag. ‘Corrected second printing’, 2006. Orig. *Histoire des mathémathiques chinoises*, Paris: Masson, 1987.

Needham, Joseph, and Wang Ling 王鈴. 1959. *Science and civilisation in China*, vol. 3: *Mathematics and the sciences of the heavens and the earth.* Cambridge: Cambridge University Press.

Qian Baocong 錢寶琮. 1932. *Zhongguo suanxue shi* 中國算學史 上卷 (‘A history of Chinese mathematics, Part 1, by Chien Pao-tsung.’). (Guoli Zhongyang Yanjiuyuan Lishi Yuyan Yanjiusuo Dankan 國立中央研究院歷史語言研究所 單刊甲種之六, A.6). Beiping: Academia Sinica. www.scribd.com/doc/285715053

Rees, Paul K., and Fred W. Sparks. 1967. *College algebra*. 5th ed. New York: McGraw-Hill.

Shen Kangshen 沈康身, John N. Crossley, and Anthony W.-C. Lun. 1999. *The nine chapters on the mathematical art: Companion and commentary*. Oxford / Beijing: Oxford University Press / Science Press. books.google.dk/books?id=eiTJHRGTG6YC

Sivin, Nathan. 2009. *Granting the seasons: The Chinese astronomical reform of 1280, with a study of its many dimensions and a translation of its records *授时曆叢考. (Sources and studies in the history of mathematics and physical sciences). New York: Springer. ‘Nathan Sivin, with the research collaboration of the late Kiyosi Yabuuti 藪內清 and Shigeru Nakayama 中山茂’. www.springer.com/gp/book/9780387789552

Wang Ling 王鈴, and Joseph Needham. 1955. ‘Horner's method in Chinese mathematics: Its origins in the root-extraction procedures of the Han dynasty’. *T’oung Pao* 43.5: 345–401. __ www.jstor.org/stable/4527405__