Talk:Horner's method

A notation for the Horner scheme

I posted the following in Talk:Ruffini's rule, but got no response. I'm reposting the content here, since it may be more relevant here:

My professor showed me this algorithm for evaluating polynomials (more) quickly, and it looks very much like synthetic division:

Suppose $f(x)=3x^{6}+5x^{3}+2x^{2}+1$ (I just made it up), and I want to know what $f(2)$ is. I setup the problem thusly,

 2 |     3     0     0     5     2     0     1
   |
   |           6    12    24    58   120   240
   |-------------------------------------------
         3     6    12    29    60   120   241

The 2 at the very left is the parameter, and the rest of the first row is the coefficients of the polynomial. The first coefficient drops down directly. Then I multiply it by the parameter to get 6, which goes to 2nd row, 2nd column. I add the columns (0 + 6) and drop down the sum. Multiply it by the parameter again yields 12, which goes to 2nd row, 3rd column, ... Repeat until the last column, and the last sum is $f(2)$

This algorithm needed 7 multiplies and 6 adds. Computing $f(x)=3(2)^{6}+5(2)^{3}+2(2)^{2}+1$ directly would need 14 multiplies and 4 adds.

Is this a variant of synthetic division, thus belongs to the aritcle? If not, where else is more appropriate? IMHO, it's pretty neat and deserves mention somewhere.

madoka 00:31, Oct 12, 2004 (UTC)

This is precisely the Horner scheme. The long-division-like notation, as far as I know, is your prof's idea.

Loisel 13:42, 14 Oct 2004 (UTC)

Actually, I was taught this table layout by a classical mathematician of the first order. He mentioned that people use this method in Europe. I assume from his background that he meant Eastern Europe. Tparameter 18:29, 9 November 2006 (UTC)

It would be nice to see synthetic division written somewhere in this article.. not everyone knows it as Ruffini's rule. Or maybe an example in the typical notation used with synthetic division. Otherwise great article! :-)

Numerical efficiency

Horner's scheme is more efficient than naive evaluation since it requires less operations. I have always read that it is also more convenient from the floating-point arithmetic point of view, but I don't see why. Can someone provide an easy example of a polynomial and a number where Horner's scheme performs better (in the sense of the relative error) than naive evaluation. Just a little example where I can follows the calculations by hand.

Old stuff

I think the first description is gibberish. I'll delete it unless someone protests. Loisel 05:17, 6 May 2004 (UTC)

Done. Loisel 04:52, 11 May 2004 (UTC)

error in formula

The formula

$p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)))$

must be written

$p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\cdots ))$

to make the number of ")" match the number of "(". Bo Jacoby 10:45, 7 March 2006 (UTC)

More numerical efficiency

It occurs to me, reading this article, that the claim about numerical efficiency is misleading. Naive evaluation of a polynomial, say

$p(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}\$

does not necessarily require

${\frac {n(n+1)}{2}}=\sum _{i=0}^{n}i$

as claimed in the article, unless one is indeed very naive. A better way to do it, and the way people actually do it, is to compute the powers successively and save the results. This requires only $n-1$ multiplications, since one is in effect computing only $x^{n}.$ One then multiplies each by its coefficient, another $n$ multiplications, and adds the results: $n$ additions. It follows then that the naive algorithm requires only $2n-1$ multiplications and $n$ additions, so Horner's method is, in terms of time complexity, not even a big-O improvement. It merely improves the "coefficient".

That's time complexity; what about space complexity? Horner's method requires only storing one number at a time, namely $b_{i}$ when computing $b_{i+1},$ after which it is no longer needed. These numbers are all about magnitude $a_{n}x^{n},$ or in terms of bits, about $\log a_{n}+n\log x.$ So one requires $O(n)$ storage space to execute Horner's algorithm. The naive algorithm again naively requires storing all the numbers $x,x^{2},\dots$ before multiplying with the coefficients and then adding, which would appear to be a space complexity requirement of $O(n^{2})$ bits (that's 1 + 2 + ...), but that's just as silly as multiplying each power of $x$ separately. One should instead perform "nested summation", namely computing successively $a_{0},a_{0}+a_{1}x,\dots ,$ which requires only remembering the previous value of $x$ and the previous iteration's partially computed sum: additional space complexity, again $O(n),$ or more specifically, about $2n\log x.$ So Horner is again just an improvement of a factor of 2.

One objection I foresee is that someone will claim that this is "changing" the naive computation by optimizing it. That's a reasonable claim for the time complexity computation, since a priori I do need all the powers of $x$ and I'm just choosing to do it cleverly. My point is, though, that if you wanted to do it on paper you would compute those powers by the method I describe; it's only when writing in some kind of programming language that you'd fall into the (easy) trap of writing something stupid like (code snippet from a likely implementation in C):

for (i = 0; i <= n; ++i) {
    poly += a[i] * pow(x, i);
}

which requires recomputing each one. And that's an issue with the representation of the algorithm rather than the algorithm itself; I maintain that the naive algorithm as it is conceived by anyone who sits down to do it is as I have described. Still, the point stands: the naive algorithm does call, apparently, for computing each power separately. It is less clear that the same objection applies to the computation of space complexity: consider that by definition of a sum, we have

$p(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}=\sum _{i=0}^{n}a_{i}x^{i},\$ where the big sigma is defined in general by:

$\sum _{i=0}^{n+1}A_{i}=\sum _{i=0}^{n}A_{i}+A_{n+1}.\$

In other words, the definition of repeated addition is as "nested addition"; this is not nearly the same league of optimization as Horner's "nested multiplication", which requires actually factoring distributed products in the polynomial. This is just the associative law, and in fact it is not even an optimization because it is required by definition of addition as a binary operation. The biggest choice made here is to write the sum in order of increasing powers of $x,$ which is already done in the statement of the problem.

This is not to diminish the value of this method. It's just to say that it isn't as much better as it would seem, unless the person doing the naive computation is really a total naif. I would correct the article, and I'm certain that I'm not the only person to have thought of this so it's probably not original research, but this is totally not my field and I don't know a reference that would have it. So I put it here instead, in case one of you knows. Ryan Reich 21:11, 13 July 2007 (UTC)

Hell, as soon as I write this I check back at the section in the article and find that something else makes reference to Knuth Vol. 2. So I check Knuth (I always do intend to read it...) and find that even before the very first algorithm in section 4.6.4, he makes precisely the observation I just made. He doesn't discuss the space complexity at all, though, except for dismissing it with a comment about accessing results in memory that really is a comment on the time complexity, so I still don't have a reference to that. I'm putting it in anyway and hoping someone else can fix this. So references are still welcome. Ryan Reich 21:15, 13 July 2007 (UTC)

Polynomial root finding

In the section on polynomial root finding, it reads:

• Given a polynomial $p_{n}(x)$ of degree $n$ with zeros $z_{n}<z_{n-1}<...<z_{1}$ make some initial guess $x_{0}$ such that $x_{0}>z_{1}$.

What isn't clear is how to determine a range for the roots (the values $z_{n}andz_{1}$) without knowing what the roots are in the first place; if there's a method, it would be nice to refer to it. It's also not obvious why the method should start with a root that's outside the range of roots - why not use the intermediate value theorem and bisect to find a starting guess? --Jay (Histrion) (talk • contribs) 02:00, 1 November 2009 (UTC)

The whole section should be erased or rewritten. The title is wrong, since the root finding invokes Newton's method as a black box. What it describes is polynomial deflation, that is, dividing off a linear factor using the Horner scheme. One would expect that the implementation of Newton's method using a two stage Horner scheme were described as well.--LutzL (talk) 08:20, 2 November 2009 (UTC)

And, to make the confusion complete, the proponents on the Ruffini's rule talk page (in the archive now) would argue that this deflation procedure is not what the Horner scheme is about. Because the long or synthetic division interpretation of the result of this algorithm in their tradition bears the name Ruffini, whereas Horner scheme solely applies to the polynomial evaluation part.--LutzL (talk) 08:26, 2 November 2009 (UTC)

History

The history really is problematic - see William George Horner, which now follows MacTutor. The 1819 date seems to be wrong, Horner may have been a plagiarist, and the claims about Chinese mathematicians, although undoubtedly well founded, depend on whom you read. Charles Matthews (talk) 09:32, 21 April 2010 (UTC)

These problems are being addressed. In particular, William George Horner is now free-standing; but see also the section below, Is Fuller's article a hoax?

Concerning the Python Implementation

The example of a Python implementation of the Horner Scheme can be slightly improved. It currently lacks comments, and takes an unnecessary input. I propose to add some comments to it and eliminate the input n, instead taking it as the length of the list a. I also propose to combine the variables n and i, as only one is necessary. These changes will make the Python function more efficient and more user-friendly.

The change would be as follows:

def Horner(a, x):
    """A function that implements the Horner Scheme for evaluating a polynomial.
    Inputs:  a, a list containing the coefficients of the polynomial
             x, the value at which the polynomial will be evaluated
    Outputs: result, the value of the polynomial evaluated at x
    """
    n = len(a)
    result = a[n]
    while n >= 1:
        result = result * x + a[n-1]
        n -= 1
    return result

Agreed -- I believe the implementation currently up is incorrect. It evaluates the coefficients backwards. 2604:2000:4081:8900:956C:2E51:27F3:B2F1 (talk) 21:40, 17 December 2017 (UTC)

Horner scheme/method

There is something distinctly wrong with calling an article Horner scheme and then saying Horner method everywhere. If the title is not the common name then try changing it to the common name, otherwise use the title. Dmcq (talk) 17:01, 4 March 2012 (UTC)

I did a quick google books on "Horner scheme" "Horner rule" and "Horner method" and the various versions with a 's or s after Horner and "Horner's method" seems to have quite a clear win so if no-one complains in the next day I'll swap the two so the title of this article is Horner's method. Dmcq (talk) 17:12, 4 March 2012 (UTC)

Well if you've come here you've seen IU've moved it! Dmcq (talk) 13:29, 5 March 2012 (UTC)

Is Fuller's article a hoax?

A. Thomas Fuller published an article, Horner versus Holdred: An Episode in the History of Root Computation that appeared in Historia Mathematica early in 1999 a few months before he died (the exact reference is Hist. Math., 26 (1999), 29–51). Although the subject and periodical were novel for him, he enjoyed a distinguished record for scholarship. The article reads in accordance with this - until you begin checking the details. The flaws that turn up are then so numerous and so strange that it is difficult to to explain them, especially give the strong undercurrent of aspertion throughout the article, not only against Horner, but against J. R. Young, Thomas Stephens Davies, Augustus De Morgan and others. Hence the question: might the article be a hoax?

Fuller cites two contemporary reviews from The Monthly Review, both now available through links in the main article, but in a partial or lopsided manner; you would never know, for example, that the reviewer is so welcoming of Horner's article. But then you would also not know from Fuller that there is a third review, also available now through the main article, that specifically looks at the booklet of Theophilus Holdred and finds it wanting. The reviewer is exceptionally well-informed and, as the main article suggests, would seem to be Peter Barlow. These reviews, taken together, upset, if they do not altogether scuttle, Fuller's advocacy of Holdred as the first published proponent of Horner's Method.

It is much the same with Fuller's quotation of the writings of J. R. Young, who, at first, drew on Holdred's booklet in his own exposition, possibly because Holdred first seems to have come to attention in The Gentleman's Mathematical Companion, where Young and Peter Nicholson, Holdred's associate-cum-rival, were both active. Reading Young more fully, we find that Fuller's presentation is biased: Young does say the things Fuller has him say, but he says a lot more. In the first place, Young acknowledges Horner's work as superior, but for his own purposes, specifically in the cubic case, he prefers to work with Holdred's formulation. But he is also at pains to assess Holdred's work, finding that Holdred's first method is that of Henry Atkinson in 1809 while his second method, inserted after Holdred's booklet had already appeared so that it had to be reissued, followed that already proposed by Horner.

Young was not alone in fancying Holdred's handling of cubics. Fuller calls attention to an obscure footnote to the same effect which Fuller holds against Augustus De Moragn. It is true that it appears in a volume sandwiched between two pieces by De Morgan, but as many library index cards make clear, and as is made explicit in the second edition, this piece is the work of one, J. Parker. Is is difficult to see how anyone has the detective skills to track down such a footnote without following up on the authorship.

But it gets worse. Fuller tells us three times of the misprints in Horner's article in 1819, without ever saying what they are, but suggesting that the propensity of others to reprint the article without correction is indicative of their lack of understanding. T. S. Davies is one of these miscreants: he reprinted the article in The Ladies' Diary for 1838, appearing in late 1837, the year Horner died. What Fuller does not tell us is that a key points throughout this reprint, Davies supplies editorial notes. So much then for someone who might not have understood the article.

Fuller also tells us that Horner, in a contribution to Leybourn's Mathematical Repository does not acnkowledge Holdred's work whereas Horner devotes an entire section of his sequence of notes to Holdred's method as it had been presented by Nicholson. Fuller is also suspect on the dating of what appears in the Repository, failing to recognize that individual issues came out sporadically, to be bound up in volumes, with four to a volume - problems with Glendinning the printer meant that the fourth volume appeared in 1819 but the fifth only in 1830.

There is more, but I shall leave off here, in the hope that someone can answer the question.

The answer is that it is not a hoax For omissions and bias you could only make the accusation of careless non-objective work. You cannot make another wild accusation of a hoax without a shred of evidence. So I think you should withdraw the word 'hoax' which is defamatory and against the spirit of Wikipedia. If what you say is true, there are no doubt reasons for it which you might have used your detective skills to find. For example, Fuller was retired and, as can be seen from his address given in the paper, was living in the countryside. So he might not have had the same excellent library services as you obviously enjoy. And, as you observed, he wrote shortly before his death so other reasons may easily be imagined. It is not unusual for older people to be less mentally alert. And again assuming everything you say is true, you still have not proved your case because you limit yourself to the who-said-what-when about someone else’s work. You do not appear to have done, as Fuller did, the harder work of reading and understanding the ideas in the quoted works. Have you, for example, actually read and understood Horner 1819 and Holdred 1820 in the original? If so, which is closer to what is nowadays called 'Horner's method' ? — Preceding unsigned comment added by JFB80 (talk • contribs) 19:13, 16 July 2012 (UTC)

We must be grateful to JFB80 for coming forward to help with these enquiries. It is to be hoped that others will do so. For example, as JFB80 no doubt noticed, A. Thomas Fuller acknowledges at the end of his paper two anonymous referees and a J. F. Barrett. So, there may, indeed, be others, familiar with either Fuller or his paper, who can help.

I should like to take this opportunity of reassuring JFB80 and other concerned readers that we are only at the stage of questioning. With all due respect, a question is not a wild accusation, neither can it of itself be held to be defamatory. As for the word 'hoax' it would not appear to be against the spirit of Wikipedia if the entry Sokal affair is anything to go by: for some, being the perpetrator of a hoax is a badge of honour - so it might be for A. Thomas Fuller, as much as it is for Alan Sokal. Of course, it might be that Fuller was incompetent or incapacitated, possibly lapsing into senescence or otherwise not in the best of health, but I should merely put it to JFB80 such possibilities might be far more detrimental to Fuller's reputation than, say, the suggestion that he was a prankster.

Does JFB80 know of anything in the record to indicate that Fuller was mentally less acute than he had been at the University of Cambridge or that, in his rural retreat in Hampshire - in communting distance for the University of Southampton, Brighton for the University of Sussex at Falmer, and London, for the British Library among many others - he was any less in contact with library services than he had been? At first blush, his paper does not read as if there were anything untoward in those regards; for that matter, it did get by the referees and editors into print, where it has gone on to be quoted.

JFB80 seems to want to have things both ways, going on to insist that Fuller did the harder work of reading and understanding the ideas in the quoted works, as though someone who points out flaws in Fuller's paper, showing that Fuller's reading and understanding was repeatedly unsound, might not be so diligent. We are not involved with some kiss-and-tell story, a matter of who-said-what-when about someone else’s work, and to suggest otherwise, as JFB80 seems to, is to impugn the scholarly judgement of the reviewer for The Monthly Review, J. R. Young and others gratuitously, although, of course, that is exactly what Fuller is inclined to do, as though the only person capable of reading and understanding is Fuller himself. Let us recall that Fuller was a distinguished scholar with a strong reputation of meticulous research, a denizen of libraries who would know, not to check just one volume of a periodical, but a run of volumes on either side; not to check just one edition, but successive editions, who prided himself on such attention to detail, and who would pounce on anyone not coming up to this standard. How does someone of this calibre miss the denouement in s sequence of reviews to which he has called attention by quoting the opening episodes?

Readers of the main article can now go to all three parts of the sequence and make their minds up for themselves. As for Horner's paper of 1819, I have also put in place a link which I hope will make it more directly accessible. I regret not having Holdred's booklet in both editions in a form that can readily be made available. In the meantime, JFB80 might like to rest reassured that it was the discovery that A. Thomas Fuller gave evidence against himself of not having understood Horner's article that prompted further investigation of Fuller's other assertions. If I have written about these later findings first of all, that is only because they are so passing strange.

But, once again, let me leave off here, in the hope that others will be coming forward to assist with enquiries.

(1) You criticise Fuller by quoting reviews from Monthly Review which you say 'scuttle' him. The 1st review (1820 vol 91) you quote from, which praises Horner, is not the same as 2nd review (1820 vol.93) Fuller quotes from, which has much less praise. It is true that Fuller does not mention the praise of the 1st review but praise does not settle the priority question which was discussed at length in the 3rd review (1821 vol.96) which you do not comment on. Concerning this 3rd review you say But then you would also not know from Fuller that there is a third review, also available now through the main article, that specifically looks at the booklet of Theophilus Holdred and finds it wanting. But what that 3rd review actually said was the opposite - Mr. Holdred has unquestionably left 'nothing to be desired', for the solution is complete in all its points: but the author is unknown; .... and the consequence is that little or no notice is taken of a solution which would, in the glowing language of some of our foreign neighbours, have conferred immortality on an Euler or a Lagrange. What a difference! This queries your credibility and unscuttles Fuller. A pity he did not know of this review. (2) When you were writing, it looks as though you did not realize that the 'Horner method' in question - the one Fuller was talking about (synthetic-division algorithm for root-shifting) - was then not described in the Wikipedia article. For this you have to go to the excellent French version Méthode de Ruffini-Horner. (3) Fuller did travel while his health permitted, even to the National Library in Paris. By contrast you have been able to quote material easily available to you on the internet, a convenient facility not available to Fuller. JFB80 (talk) 20:55, 15 June 2014 (UTC)

I notice that the links to the papers of Horner and to the Monthly Reviews are now disabled and give "Not found" when clicked. Very mysterious. As I believe you put these links in, please restore them.JFB80 (talk) 20:02, 14 July 2014 (UTC)

JFB80 is clearly determined to see Fuller unscuttled. Sadly, JBF80 does this by latching onto a comment above, rather than in the main article; quoting selectively from the third review, which somehow Fuller never mentioned; and then adjusting the main article accordingly. But we must always be careful for what we wish: JFB80 thinks it a pity that Fuller did not know of this review; and pity, indeed, because, as the main article suggested, before being rewritten by JFB80, it provides a contemporary view that authoritatively, but judiciously, controverts the thesis that Fuller tried to develop, namely, that Horner did not publish 'Horner's method' (synthetic-division algorithm for root-shifting) until after Holdred had, raising the spectre of `plagiarism', and hinting that Horner may have had some mental impairment or character defect.

The reviewer certainly is generous in personal assessment of Holdred; and there is a reason for that that comes at the end of the review, which might be worth including here, as perhaps JFB80 did not get that far in his reading:

Unfortunately, it appears but too plainly by a short advertisement delivered with the present work to the subscribers, that [Holdred] has not been one of fortune's favourites; and we sincerely wish that this notice may be the means of increasing the demand for his pamphlet, which certainly displays the efforts of a strong but unassisted genius, and exhibits the solution of one of the most interesting problems in analysis.

Nevertheless, the reviewer had another aim, stated briefly in the second paragraph, which might be overlooked, if, like JFB80, you pause to savour the magnificent prose of the opening paragraph:

We shall therefore confine ourselves, in the present article, to an examination of the title of [Holdred, Holdred, and Nicholson] to the honours of the discovery.

Of course, if, like JFB80, you have an eye out for Holdred - and unscuttling Fuller - it is natural to jump over the second and third paragraphs, to further generous remarks about Holdred. But, at the risk of being tedious and nitpicking - not to mention raising questions of credibility - there does seem to be a passage in the third paragraph, pertinent to Fuller's thesis, and the likely basis for what was written in the main article, before JFB80 thoughtfully rewrote it:

We have seen the letter to Mr. Barlow, which is dated Bath, Aug. 18th, 1817, and which contains unquestionable proof that Mr. Horner was at that time in possession of his method of solution; and, as it does not appear that Mr. Holdred had shewn his solution to any person before June, 1818, it follows that Mr. Horner is very unjustly accused of this plagiarism. He was doubtless the original inventor of his own mode of solution; and although he has very unnecessarily involved its theory in some intricacy, its practical application is much more simple than the original method of Mr. Holdred. As to the method given by the latter gentleman in his Appendix, it is too much like that of Mr. Horner to allow any credit to be taken by him for it; Mr. Horner's paper having been published some months before this Appendix was sent to press.

The third review is long: two pages, in five paragraphs. Some readers might follow JFB80 in sampling just the first and fourth paragraphs. There is no doubt that they are excellent paragraphs, well worth reading. If, however, you put back the second, third and fifth paragraphs, it would seem that you do come out with the account presented in the main article, before JFB80 changed it.

Now, if this were also how Fuller worked, much would fall into place: knowing the first two reviews, but not the third; but also the seemingly strange use of other sources, as alluded to earlier. No amount of travel, even to the National Library in Paris, when health permitted, would likely alter such habits of research.

But the third review has a further importance for the discussion. The third review, while generous to Holdred, and full of praise for his efforts, yet accords priority, in publication and credit, to Horner, seeing insufficient difference even in the method Holdred published in his Appendix after Horner's paper had been out some months to tilt the balance to Holdred. It is known that the key mathematical reviewer for the Monthly Review had been Peter Barlow. The third review reveals acquaintance of correspondence between Horner and Barlow. A natural surmise then would be that Peter Barlow was the reviewer. If so, this weighing up of matters would be the view of one of the leading exponents of approximation of the day, perhaps all the more telling because the discovery had not been made by one of the leading exponents of approximation of the day. At the very least, the reviewer is presumably someone in the circle of Barlow.

Part of being a leading exponent of approximation is the recognition that methods of approximation allow variants which may have competing advantages. For the reviewer, Horner still has a method simpler to apply than Holdred's original method, depite decking it out in what the reviewer thinks, qua applicatication, unnecessary detail. Holdred, on the other hand, is found wanting in not making early simplification, besides also not publishing in a timely manner. The problem here is that had Holdred published when he first had his ideas, they would likely enough have been more complicated, for want of revision and polish, and might well have sunk with little trace. Horner himself reports finding earlier partial solutions that he readily acknowldege foreshadowed his own approach - even at the end of his paper in 1819, he is at pains to footnote Exley's method of solving cubics. We might also remember the experience of Henry Atkinson. J. R. Young found Atkinson's method (from c. 1809) to be the same as Holdred's original method, but Atkinson was advised by Barlow's senior colleague, Charles Hutton, a fellow of the Royal Society from 1774, that, while he could publish, his publication would have no impact. (It would seem, from this, for what it is worth, that Atkinson thus has priority in communication, seeing that Holdred never told anyone about his method until 1818.) It might be worth noting that Barlow himself was only elected FRS in 1823, so, in 1821, might not have been fully apprised of any modifications to Horner's presentation of his method required to secure publication in Philosophical Transactions in 1819. Had Barlow been a fellow of the Royal earlier, things might have been different for Horner - and for Holdred. But, if you look at what was available in English before 1819, including the publications of Hutton and Barlow, you can see the difference Horner's paper made, whatever its defects. After 1819, many others piled in - and still do pile in.

It would seem really too bad if Fuller did not know the third review.

A further puzzle in Fuller's article is that, although he was an experienced researcher, he did not seem to allow for this aspect of the environment of research, in which everyone wants to promote their own twist on the topic. The reviewer for the Monthly Review seems to have this more nearly right, not just for 1821, but for the way in which the phrase `Horner's method' has come to be used.

Again, perhaps JFB80 is not seeing this in bringing in writers from Italy and France. In the first place, the main article, in a section left untouched by JFB80, shows some familiarity with Wikipedia in Italian, as well as French. What is perhaps amusing here is the narrow awareness of the literature in French that those articles show. Consequently, JFB80 may be unaware that the origins of what he terms the 'synthetic-division algorithm for root-shifting' is very much a matter of debate, and was keenly debated, for example, by J. R. Young, T. T. Wilkinson, and T. S. Davies. This is exactly why the question of Horner's access to the work of Budan, who does give instances of the algorithm, is significant. The irony is that, had Fuller attended to this other literature, he might have been able to build at least a more illuminating case, if not also a stronger one. But, then if Budan is not altogether written out of the account in French and Italian, then he is certainly downplayed, even more effectively than Horner has been belittled in English as a 'school teacher', never mind Holdred.

I fear that JFB80 is bringing in yet another red herring here, but certainly, for a fuller treatment, further account needs to be given to authors from Italy and France.

Holdred (1820)

JFB80 and other readers might care to note that the bibliography in the article now provides a link to Holdred's booklet. Although the identity of this Theophilus Holdred remains somewhat obscure, it may be worth noting the baptism at St. Giles in the Fields on 27 April, 1760 of Theophilus, son of Theophilus and Alice Holdred, as fitting exactly the right time frame and in the approximate vicinity in London where Holdred is known from his mathematical contribitions, first of all Vere Street, Lincolns Inn Fields and then Denzel Street, Clare Market. The couple, Theophilus and Alice, had an older son, Thomas, whose baptism, also at St. Giles in the Fields, is recorded for 9 January, 1758.

It is hoped that readers with further information on Holdred will come forward to record it here.

History section

Isn't the whole precedence discussion in the history section completely misplaced? What we call "Horner scheme" or "Ruffini something" (scheme, rule, method) is the nested evaluation of a polynomial as described in the article. This method or idea is shortly hinted at at the start of the Horner 1819 paper and attributed to Lagrange. The rest of the paper is a method for the manual application of Newton's original method for the approximation of polynomial roots using Taylor shifts implemented via repeated applications of the "Horner scheme", Descartes rule of signs resp. extended use of sign variations and rounding. And this method of root approximation is the subject of the precedence discussion, not the polynomial evaluation method and other trivialities connected to it that probably were common knowledge at the epoch.--LutzL (talk) 12:14, 14 February 2015 (UTC)

As you say what is nowadays understood as Horner's method is the nested evaluation of polynomials. The older meaning as a method of root extraction seems to have almost gone out of use. It was this older meaning that what the subject of the above discussion and of Fuller's paper. The method is explained clearly for example in the book 'Calculus of Observations' by Whittaker & Robson which is quoted in the references (available online). I think you will find that this was essentially also what Ruffini was talking sbout. What Fuller was saying was that the convenient tabular method for root shifting was first clearly stated, not by Horner 1819 but by Holdred 1820 and this is what all the fuss was about. As far as I can understand,Fuller was quite correct. You just have to have the courage to struggle through the algebra to find out for yourself. JFB80 (talk) 07:57, 25 February 2015 (UTC)

That was not my problem, I know about Taylor shifts, FFT tricks to accomplish it etc. and why they are not really necessary to implement Newton's method for polynomials (which is possibly called Birge–Vieta's method) -- even if the full shift is used in the method that Newton originally described, in the tradition of Viete etc.

My problem was and is the disconnect between the stated content of the article that is in line with the modern naming tradition and a seemingly unrelated dissertation on the history of a topic that is not declared in the article. Either the article needs the addition of fully shifted method including sign rules and other manual tricks or the history section needs to be reduced to the relevant contents that this polynomial evaluation method was common knowledge dating back to at least Lagrange if not Newton and that the naming is a regrettable historical accident.--LutzL (talk) 14:01, 25 February 2015 (UTC)

I agree that the article needs rewriting but I think it should be balanced and include both the modern view and the historical view. Before the computer age there was a need to solve polynomial equations by pencil and paper or by using a hand calculator. What was known as "Horner's method" was the most used method of root extraction. Since equations were usually low order e.g.3 the nested polynomial method was not essential, in fact Horner himself did not apparently use it in the numerical examples he gave to illustrate the method. That is basically the history. O course the naming is quite wrong and unjust and that should be made clear in an encyclopedia. JFB80 (talk) 20:33, 25 February 2015 (UTC).

In myy opinion, Horner used the recursive evaluation scheme, but did not find it worth to extensively document this computation trick step-by-step in the short length of the paper beyond its first mention. The examples contain condensed tables of intermediate results that are actually used in the computation or decision-making. I believe that the method was also used for higher degree polynomials, but such examples would have been too long for the paper.--LutzL (talk) 14:56, 27 February 2015 (UTC)

You state your opinion but you have no evidence. As you are good with computng why not see if you can reproduce Horner's calculations? I did look at one cubic calculation and it seemed to me that it had similarities with "Horner's method" but it was not the same. It is difficult to decypher what he did though. JFB80 (talk) 04:56, 1 March 2015 (UTC)

'Later remark: I didmt answer your point about the 'seemingly unrelated dissertation'. Yes it was declared in the article but only in the history section where there was written a glowing account of Horner's 1819 paper (which was about root extraction not polynomial evaluation). I didnt start this discussion, the other anonymous person did.JFB80 (talk) 08:24, 27 February 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Horner's method/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

The Horner scheme provides a fundamental result on the complexity of polynomial evaluation.--LutzL (talk) 08:36, 5 December 2007 (UTC)

Substituted at 18:02, 5 June 2016 (UTC)

The classical Chinese version of Horner’s methodDbwagner (talk) 14:48, 13 January 2017 (UTC)

Some may be interested in this article:

"The classical Chinese version of Horner’s method: Technical considerations", 12 January 2017, http://donwagner.dk/horner/horner.html Dbwagner (talk) 14:48, 13 January 2017 (UTC)

This Article is about Two Different Algorithms

As the heading suggests, there are two Horner Methods, doing two significantly different things. Currently, the article's structure is misleading. The Horner's_method#Description_of_the_algorithm section refers only to the more well-known, polynomial application. Then the Horner's_method#Examples section is divided to an application of the first algorithm (Horner's_method#Floating_point_multiplication_and_division, and a description of the second (root finding) algorithm (Horner's_method#Polynomial_root_finding). This subsection continues with code examples, again, of the first algorithm.

The current structure is confusing and inconsistent. I suggest to split this article into two. This article should refer to the polynomial application algorithm, while another page should be opened to describe the root-finding algorithm. Proper disambiguation comment should be made at the top of each of these pages. — Preceding unsigned comment added by 194.9.245.37 (talk) 07:33, 22 May 2018 (UTC)

You are quite correct although the article does say clearly at the beginning that there are two algorithms. But since the polynomial evaluation algorithm is also used for the root extraction algorithm couldn't this be described first, making it quite clear that the root finding algorithm has gone out of use with the introduction of computers and that to most people nowadays Horner's Method just means (incorrectly) the polynomial evaluation method. — Preceding unsigned comment added by JFB80 (talk • contribs)

I am a bit confused. If the article is about two separate algorithms built one on top of the other, the algorithm description should describe both algorithms. The description in this article only describes one. The other algorithm is briefly described in Horner's_method#Polynomial_root_finding, which is located under the "Examples" section (not an algorithm description). Furthermore, the Horner's_method#Polynomial_root_finding section continues with code examples for the first algorithm. It seems to me that the root-finding algorithm has been improperly added to this article. I believe the Wikipedia best-practice on this matter is that different algorithms (even-though related) should be given their own articles. Alternatively I would suggest to not talk about the root-finding algorithm as a separate algorithm in the introduction, but rather as an application. In any case, the code examples are now improperly located in the article and have to move. Brosenan (talk) 19:19, 23 May 2018 (UTC)

Near the beginning of his original highly obscure 1819 article, Horner described the polynomial- evaluation algorithm (which he ascribed to Lagrange but actually known centuries ago by the Arabs, Chinese, etc.). He went on to describe a root extraction method with similarities to that later called "Horner's Method" by de Morgan. In "Horner's Method" the root-finding algorithm incorporates the polynomial-evaluation algorithm in the tabular method by which the calculation is carried out. This is well described e.g. in Whittaker & Robson's's "Calculus of Observations" (available online). In this way the two algorithms are connected. JFB80 (talk) 11:59, 24 May 2018 (UTC)

In modern algorithmic, the method for evaluating polynomials is better known as Horner's rule and Horner's scheme. So, I have changed the order in the first sentence. I have also removed the regional restrictions, as "Horner's rule" and "Horner's scheme" are used in many international publication whose authors are not specifically American of English.

Also, it seems old-fashioned (at least) of using "Horner's method" for referring to the use of Horner's rule for implementing Newton's method for polynomials. So, I have rewritten the lead for giving less importance to this. Horner method.

From this discussion, it is clear that the body of the article needs to be reorganized and rewritten. Also, per MOS:CODE and MOS:MATH#Algorithms, the numerous codes must be removed, and possibly replaced one (or two) implementation in pseudocode. Two may be useful as the implementation depends on the method of storage of the coefficients (linked lists or arrays). The given implementation are confusing as the storage method is not clearly given. As I have not the time for that, I have tagged the article with {{cleanup}} D.Lazard (talk) 20:46, 22 November 2018 (UTC)

Should the article be split (or forked) into two? This polynomial evaluation method, I thought we always called it "Horner's rule", continues to have use in modern times. I do not know about the root-finding method, but if "Horner's method" is nothing other than applying the Newton–Raphson method to polynomials, I think that should be in a different article and made clear. Seems to me that ascribing to Horner a method that is nothing other than a specific case of Newton–Raphson, is more credit to Horner than historically deserved. 50.47.109.19 (talk) 00:32, 12 December 2018 (UTC)

I do not think that a separate article is needed. My opinion is that Horner's method is notable only from an historical point of view. This opinion is enforced by the fact that, except for MathWorld article (ref. 3), sources are mainly historical. Even in MathWorld article, the method is described in the style of 19th century, and it is only at the end that it is said that is is related with divided differences. We lack of a description of the method in a modern algorithmic language and of a report of a computer implementation. So this seems not enough for a separate article. Nevertheless, I am not sure that my description of Horner's method in the lead (use of Horner's rule in Newton's method) is accurate. I deduced it from the previous lead, from the mention of Horner's method in Root-finding algorithm, and from a quick look on Horner's paper. So the sentence describing the method in the lead may require to be changed. In summary, my opinion is that Horner's method needs to be mentioned in Wikipedia, but its notability is not enough for a separate article. D.Lazard (talk) 09:21, 12 December 2018 (UTC)

Well, "Horner's Rule" for evaluating polynomials:

${\begin{aligned}p(x)&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}\\\end{aligned}}$

has current (and ongoing) value for practical mathematical computation. I am not absolutely certain, but I believe it is the standard optimal method of evaluating a polynomial for a given x when the numerical values of the coefficients are know. But it seems like the root-finding method (which we are told is just the Newton-Raphson method) is different and confuses the issue. 50.47.109.19 (talk) 02:29, 13 December 2018 (UTC)

I will probably be completely ignored, but it needs to be remarked that the present description of the root-finding method is completely wrong. The method is based on a tabular layout. The section on the root-finding method needs to be completely written together with the computer programs. If you doubt this, check with a reliable source, e.g. the book of Whittaker and Robson quoted in the references (available online). JFB80 (talk) 20:17, 13 December 2018 (UTC)

To editor JFB80: I agree that the description of the root-finding method must be either removed (that is reduced to a single sentence for linking to a source) or rewritten in a modern algorithmic language. Nevertheless, you are wrong when saying "The method is based on a tabular layout". The "tabular layout" is simply a generalization of Horner's rule for computing the coefficients of the polynomial $P(x+r)$ with $n(n-1)/2$ additions and multiplications by r. Horner's root-finding method uses this algorithm and its intermediate results, but could work with any algorithm for this change of variable. Unfortunately, we lack of a description of Horner's root-finding method in terms of an iterative algorithm. Thus a modern description of the method would probably WP:OR. Nevertheless, because of this, I have removed the mention of Newton's method in the lead.

Here is a description of Horner's tabular process in modern terms: Let $P_{i}(x)=a_{n-i}+a_{n-i+1}x+\cdots +a_{n}x^{i}.$ Let $Q_{i}(x)=P_{i}(x+r).$ One has $Q_{0}(x)=P_{0}(x)=x_{n},$ and for i > 0, one has

$Q_{i}(x)=P_{i}(x+r)=a_{n-i}+(x+r)P_{i-1}(x+r)=a_{n-i}+(x+r)Q_{i-1}(x).$

So, the list of the coefficients of $Q_{i}-a_{n-i}$ is obtained by adding to the list of coefficients of $Q_{i-1}$ the same list shifted by one and multiplied by r. This is what is done in Horner's tabular description. It should be noted that, in Whittaker and Robson, it is quoted that $P_{n}(r)/P_{n}'(r)$ (quantity that is used in Newton's method) is the ratio of the coefficients of degree 0 and 1 of $Q_{n}(x).$ However, it is not noted that this is a bad method for computing this ratio, as it uses $O(n^{2})$ operations, while applying Horner's rule for computing $P_{n}(r)$ and $P_{n}'(r)$ separately needs only $O(n)$ operations.

This method for a linear change of variable in a polynomial is classical. I ignore whether it has a name in modern literature, and whether is was known before Horner. But it deserves to be described in WP, and for the moment, it seems that the better place would be here in a section "Generalization". Presently, I have not the time for editing this article (except for the lead). So, I leave this article in its messy state. D.Lazard (talk) 10:57, 14 December 2018 (UTC)

I have rewritten the introduction, I hope that it will be accepted like this. It just describes what has happened. As for the root-finding part I think it should start by describing the tabular method which is what was used (This is after all an encyclopedia) Afterwards it could talk about computer implementations and this should avoid 'own research' and be based on what has been published.

JFB80 (talk) 17:37, 14 December 2018 (UTC)

To editor JFB80: There should be a WP:LEAD before the table of content. I suggest to restore the previous lead and rename "History" or "Brief history" the new introduction. By the way, there is already a history section, but it deserves to be removed as consisting essentially WP:OR (historical details that are not interesting here, mentioning many non-notable people without any indication of the reasons for citing them, lack of citations of reliable secondary sources, most primary sources referring to dead links, etc.). D.Lazard (talk) 18:35, 14 December 2018 (UTC)

Added link between theory and application

I added the expression

$p(x)=(b_{1}+b_{2}x+b_{3}x^{2}+b_{4}x^{3}+\cdots +b_{n-1}x^{n-2}+b_{n}x^{n-1})(x-x_{0})+b_{0}$

as a link between theory and application (examples). This expression is of course empirically true, but can anyone prove it mathematically? That proof is vital, because otherwise this article is only really about Horner's rule, not Horner's method. Tavernsenses (talk) 09:00, 26 September 2019 (UTC)

Relationship with the article "Polynomial evaluation"

I have created the article Polynomial evaluation. It also covers Horner's rule, since it's pretty short to describe. Would it make sense to make Horner's method all about the division algorithm and refer to Polynomial evaluation for the evaluation method? Thomasda (talk) 12:21, 30 May 2021 (UTC)

Many people know Horner's rule under the name of Horner. So the description of the method must be in an article named after Horner (see WP:LEAST). As the method is pretty short to describe, there is no harm to have it described several times in Wikipedia, if all descriptions are linked to the main one. Normally this is done with a template {{main|Horner's method}} at the top of secondary descriptions. In Polynomial evaluation, I have used {{see also|Horner's method}} instead, because Horner's method requires to be improved for not being confusing. D.Lazard (talk) 12:51, 30 May 2021 (UTC)

Efficiency?

Whilst Horner's method is clearly optimal for calculations done manually by a single human, it's also clearly the least parallelizable, as operations must be performed in one specific sequence. Even just two humans working on the same evaluation could choose a faster method than this one. Martin Kealey (talk) 08:45, 10 March 2024 (UTC)