In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians.[1] After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.
The algorithm is based on Horner's rule, in which a polynomial is written in nested form:
This allows the evaluation of a polynomial of degree n with only multiplications and additions. This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.[2]
Alternatively, Horner's method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the Newton–Raphson method made more efficient for hand calculation by the application of Horner's rule. It was widely used until computers came into general use around 1970.
Polynomial evaluation and long division
Given the polynomial
where are constant coefficients, the problem is to evaluate the polynomial at a specific value of
For this, a new sequence of constants is defined recursively as follows:
(1)
Then is the value of .
To see why this works, the polynomial can be written in the form
Thus, by iteratively substituting the into the expression,
Now, it can be proven that;
(2)
This expression constitutes Horner's practical application, as it offers a very quick way of determining the outcome of;
with (which is equal to ) being the division's remainder, as is demonstrated by the examples below. If is a root of , then (meaning the remainder is ), which means you can factor as .
To finding the consecutive -values, you start with determining , which is simply equal to . Then you then work recursively using the formula:
till you arrive at .
The entries in the third row are the sum of those in the first two. Each entry in the second row is the product of the x-value (3 in this example) with the third-row entry immediately to the left. The entries in the first row are the coefficients of the polynomial to be evaluated. Then the remainder of on division by is 5.
In this example, if we can see that , the entries in the third row. So, synthetic division (which was actually invented and published by Ruffini 10 years before Horner's publication) is easier to use; it can be shown to be equivalent to Horner's method.
As a consequence of the polynomial remainder theorem, the entries in the third row are the coefficients of the second-degree polynomial, the quotient of on division by .
The remainder is 5. This makes Horner's method useful for polynomial long division.
The third row is the sum of the first two rows, divided by 2. Each entry in the second row is the product of 1 with the third-row entry to the left. The answer is
Efficiency
Evaluation using the monomial form of a degree polynomial requires at most additions and multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. The cost can be reduced to additions and multiplications by evaluating the powers of by iteration.
If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately times the number of bits of : the evaluated polynomial has approximate magnitude , and one must also store itself. By contrast, Horner's method requires only additions and multiplications, and its storage requirements are only times the number of bits of . Alternatively, Horner's method can be computed with fused multiply–adds. Horner's method can also be extended to evaluate the first derivatives of the polynomial with additions and multiplications.[3]
Horner's method is optimal, in the sense that any algorithm to evaluate an arbitrary polynomial must use at least as many operations. Alexander Ostrowski proved in 1954 that the number of additions required is minimal.[4]Victor Pan proved in 1966 that the number of multiplications is minimal.[5] However, when is a matrix, Horner's method is not optimal.
This assumes that the polynomial is evaluated in monomial form and no preconditioning of the representation is allowed, which makes sense if the polynomial is evaluated only once. However, if preconditioning is allowed and the polynomial is to be evaluated many times, then faster algorithms are possible. They involve a transformation of the representation of the polynomial. In general, a degree- polynomial can be evaluated using only ⌊n/2⌋+2 multiplications and additions.[6]
A disadvantage of Horner's rule is that all of the operations are sequentially dependent, so it is not possible to take advantage of instruction level parallelism on modern computers. In most applications where the efficiency of polynomial evaluation matters, many low-order polynomials are evaluated simultaneously (for each pixel or polygon in computer graphics, or for each grid square in a numerical simulation), so it is not necessary to find parallelism within a single polynomial evaluation.
If, however, one is evaluating a single polynomial of very high order, it may be useful to break it up as follows:
More generally, the summation can be broken into k parts:
where the inner summations may be evaluated using separate parallel instances of Horner's method. This requires slightly more operations than the basic Horner's method, but allows k-way SIMD execution of most of them. Modern compilers generally evaluate polynomials this way when advantageous, although for floating-point calculations this requires enabling (unsafe) reassociative math[citation needed].
Application to floating-point multiplication and division
Horner's method is a fast, code-efficient method for multiplication and division of binary numbers on a microcontroller with no hardware multiplier. One of the binary numbers to be multiplied is represented as a trivial polynomial, where (using the above notation) , and . Then, x (or x to some power) is repeatedly factored out. In this binary numeral system (base 2), , so powers of 2 are repeatedly factored out.
Example
For example, to find the product of two numbers (0.15625) and m:
Method
To find the product of two binary numbers d and m:
A register holding the intermediate result is initialized to d.
Begin with the least significant (rightmost) non-zero bit in m.
Count (to the left) the number of bit positions to the next most significant non-zero bit. If there are no more-significant bits, then take the value of the current bit position.
Using that value, perform a left-shift operation by that number of bits on the register holding the intermediate result
If all the non-zero bits were counted, then the intermediate result register now holds the final result. Otherwise, add d to the intermediate result, and continue in step 2 with the next most significant bit in m.
Derivation
In general, for a binary number with bit values () the product is
At this stage in the algorithm, it is required that terms with zero-valued coefficients are dropped, so that only binary coefficients equal to one are counted, thus the problem of multiplication or division by zero is not an issue, despite this implication in the factored equation:
The denominators all equal one (or the term is absent), so this reduces to
or equivalently (as consistent with the "method" described above)
In binary (base-2) math, multiplication by a power of 2 is merely a register shift operation. Thus, multiplying by 2 is calculated in base-2 by an arithmetic shift. The factor (2−1) is a right arithmetic shift, a (0) results in no operation (since 20 = 1 is the multiplicative identity element), and a (21) results in a left arithmetic shift.
The multiplication product can now be quickly calculated using only arithmetic shift operations, addition and subtraction.
The method is particularly fast on processors supporting a single-instruction shift-and-addition-accumulate. Compared to a C floating-point library, Horner's method sacrifices some accuracy, however it is nominally 13 times faster (16 times faster when the "canonical signed digit" (CSD) form is used) and uses only 20% of the code space.[7]
Other applications
Horner's method can be used to convert between different positional numeral systems – in which case x is the base of the number system, and the ai coefficients are the digits of the base-x representation of a given number – and can also be used if x is a matrix, in which case the gain in computational efficiency is even greater. However, for such cases faster methods are known.[8]
Polynomial root finding
Using the long division algorithm in combination with Newton's method, it is possible to approximate the real roots of a polynomial. The algorithm works as follows. Given a polynomial of degree with zeros make some initial guess such that . Now iterate the following two steps:
Using Newton's method, find the largest zero of using the guess .
Using Horner's method, divide out to obtain . Return to step 1 but use the polynomial and the initial guess .
These two steps are repeated until all real zeros are found for the polynomial. If the approximated zeros are not precise enough, the obtained values can be used as initial guesses for Newton's method but using the full polynomial rather than the reduced polynomials.[9]
Example
Polynomial root finding using Horner's method
Consider the polynomial
which can be expanded to
From the above we know that the largest root of this polynomial is 7 so we are able to make an initial guess of 8. Using Newton's method the first zero of 7 is found as shown in black in the figure to the right. Next is divided by to obtain
which is drawn in red in the figure to the right. Newton's method is used to find the largest zero of this polynomial with an initial guess of 7. The largest zero of this polynomial which corresponds to the second largest zero of the original polynomial is found at 3 and is circled in red. The degree 5 polynomial is now divided by to obtain
which is shown in yellow. The zero for this polynomial is found at 2 again using Newton's method and is circled in yellow. Horner's method is now used to obtain
which is shown in green and found to have a zero at −3. This polynomial is further reduced to
which is shown in blue and yields a zero of −5. The final root of the original polynomial may be found by either using the final zero as an initial guess for Newton's method, or by reducing and solving the linear equation. As can be seen, the expected roots of −8, −5, −3, 2, 3, and 7 were found.
Divided difference of a polynomial
Horner's method can be modified to compute the divided difference Given the polynomial (as before)
proceed as follows[10]
At completion, we have
This computation of the divided difference is subject to less round-off error than evaluating and separately, particularly when . Substituting in this method gives , the derivative of .
History
Qin Jiushao's algorithm for solving the quadratic polynomial equation result: x=840[11]
Horner's paper, titled "A new method of solving numerical equations of all orders, by continuous approximation",[12] was read before the Royal Society of London, at its meeting on July 1, 1819, with a sequel in 1823.[12] Horner's paper in Part II of Philosophical Transactions of the Royal Society of London for 1819 was warmly and expansively welcomed by a reviewer[permanent dead link] in the issue of The Monthly Review: or, Literary Journal for April, 1820; in comparison, a technical paper by Charles Babbage is dismissed curtly in this review. The sequence of reviews in The Monthly Review for September, 1821, concludes that Holdred was the first person to discover a direct and general practical solution of numerical equations. Fuller[13] showed that the method in Horner's 1819 paper differs from what afterwards became known as "Horner's method" and that in consequence the priority for this method should go to Holdred (1820).
Unlike his English contemporaries, Horner drew on the Continental literature, notably the work of Arbogast. Horner is also known to have made a close reading of John Bonneycastle's book on algebra, though he neglected the work of Paolo Ruffini.
Although Horner is credited with making the method accessible and practical, it was known long before Horner. In reverse chronological order, Horner's method was already known to:
Qin Jiushao, in his Shu Shu Jiu Zhang (Mathematical Treatise in Nine Sections; 1247), presents a portfolio of methods of Horner-type for solving polynomial equations, which was based on earlier works of the 11th century Song dynasty mathematician Jia Xian; for example, one method is specifically suited to bi-quintics, of which Qin gives an instance, in keeping with the then Chinese custom of case studies. Yoshio Mikami in Development of Mathematics in China and Japan (Leipzig 1913) wrote:
"... who can deny the fact of Horner's illustrious process being used in China at least nearly six long centuries earlier than in Europe ... We of course don't intend in any way to ascribe Horner's invention to a Chinese origin, but the lapse of time sufficiently makes it not altogether impossible that the Europeans could have known of the Chinese method in a direct or indirect way."[20]
Ulrich Libbrecht concluded: It is obvious that this procedure is a Chinese invention ... the method was not known in India. He said, Fibonacci probably learned of it from Arabs, who perhaps borrowed from the Chinese.[21] The extraction of square and cube roots along similar lines is already discussed by Liu Hui in connection with Problems IV.16 and 22 in Jiu Zhang Suan Shu, while Wang Xiaotong in the 7th century supposes his readers can solve cubics by an approximation method described in his book Jigu Suanjing.
^Analysis Per Quantitatum Series, Fluctiones ac Differentias : Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Anno MDCCXI, p. 10, 4th paragraph.
^Newton's collected papers, the edition 1779, in a footnote, vol. I, p. 270-271
Berggren, J. L. (1990). "Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat". Journal of the American Oriental Society. 110 (2): 304–309. doi:10.2307/604533. JSTOR604533.
Directly available online via the link, but also reprinted with appraisal in D.E. Smith: A Source Book in Mathematics, McGraw-Hill, 1929; Dover reprint, 2 vols, 1959.
Knuth, Donald (1997). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. pp. 486–488 in section 4.6.4. ISBN978-0-201-89684-8.
Kripasagar, Venkat (March 2008). "Efficient Micro Mathematics – Multiplication and Division Techniques for MCUs". Circuit Cellar Magazine (212).
Libbrecht, Ulrich (2005). "Chapter 13". Chinese Mathematics in the Thirteenth Century (2nd ed.). Dover. ISBN978-0-486-44619-6. Archived from the original on 2017-06-06. Retrieved 2016-08-23.
Mikami, Yoshio (1913). "Chapter 11. Ch'in Chiu-Shao". The Development of Mathematics in China and Japan (1st ed.). Chelsea Publishing Co reprint. pp. 74–77.
Mercedes-Benz W223InformasiProdusenDaimler AGMasa produksi2020–sekarangPerakitanJerman: SindelfingenIndia: Pune, Maharashtra[1]Indonesia: Bogor (MBI)Thailand: Samut Prakan (TAAP)Bodi & rangkaKelasmobil ukuran penuh mobil mewah (F)Bentuk kerangka4-pintu SedanTata letakMesin depan, Penggerak roda belakang atau Mesin depan, Penggerak 4 roda (4Matic)Mobil terkaitMercedes-Benz W206Penyalur dayaMesinBensin:3.0 L M256 I6 turbo4.0 L M176 V8 biturboBensin plug-in hybrid:3.0 L M256 I6 t…
Lisa LoringLoring diwawancarai pada tahun 2009 untuk Count Gore de VolLahirLisa Ann DeCinces(1958-02-16)16 Februari 1958Kwajalein, Kepulauan MarshallMeninggal28 Januari 2023(2023-01-28) (umur 64)Burbank, California, Amerika SerikatWarga negaraAmerikaPekerjaanPemeranDikenal atasWednesday Addams dalam The Addams FamilySuami/istriFarrell Foumberg (m. 1973; c. 1974) Doug Stevenson (m. 1981; c. 1983)…
Contea di Broomelocal government areaShire of Broome LocalizzazioneStato Australia Stato federato Australia Occidentale AmministrazioneCapoluogoBroome TerritorioCoordinatedel capoluogo17°57′43″S 122°14′10″E / 17.961944°S 122.236111°E-17.961944; 122.236111 (Contea di Broome)Coordinate: 17°57′43″S 122°14′10″E / 17.961944°S 122.236111°E-17.961944; 122.236111 (Contea di Broome) Altitudine7 m s.l.m. Superficie55 796…
Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Grigori RoshalГригорий Львович РошальBerkas:Grigori Roshal.jpgLahir(1899-10-21)21 Oktober 1899Novozybkov, Kegubernuran Chernigov, Kekaisaran RusiaMeninggal11 Januari 1983(1983-01-11) (umur 83)PekerjaanSutradaraPenulis naskahTahu…
Animal skin treated for human use A hide or skin is an animal skin treated for human use. The word hide is related to the German word Haut, which means skin. The industry defines hides as skins of large animals e.g. cow, buffalo; while skins refer to skins of smaller animals: goat, sheep, deer, pig, fish, alligator, snake, etc. Common commercial hides include leather from cattle and other livestock animals, buckskin, alligator skin and snake skin. All are used for shoes, clothes, leather bags, b…
Rudderow-class destroyer escort History United States NameUSS Leslie L. B. Knox NamesakeLeslie L. B. Knox BuilderBethlehem Hingham Shipyard Laid down7 November 1943 Launched8 January 1944 Commissioned22 March 1944 Decommissioned15 June 1946 Honors andawardsthree battle stars FateScrapped, 1973 General characteristics TypeRudderow-class destroyer escort Displacement1,740 tons (1,770 metric tons) (fully loaded) Length306 ft (93.3 m) (overall) Beam36 ft 6 in (11.1 m) Draft1…
Russian politician In this name that follows Eastern Slavic naming customs, the patronymic is Viktorovich and the family name is Chizhov. You can help expand this article with text translated from the corresponding article in Russian. (February 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accur…
1992 studio album by Joan BaezPlay Me BackwardsStudio album by Joan BaezReleasedOctober 1992RecordedNashville, 1992GenreFolk-pop, country popLength36:19LabelVirgin[1]ProducerWally Wilson, Kenny GreenbergJoan Baez chronology Speaking of Dreams(1989) Play Me Backwards(1992) Rare, Live & Classic(1993) Play Me Backwards is an album by the American musician Joan Baez, released in 1992.[2] The album was nominated for a Grammy for Best Contemporary Folk Recording.[3]…
1812 siege during the Peninsular War For the earlier battle, see Siege of Burgos (1475). Siege of BurgosPart of the Peninsular WarThe Siege of Burgos, by François Joseph HeimDate19 September – 21 October 1812[1]LocationBurgos, Spain42°21′N 3°42′W / 42.350°N 3.700°W / 42.350; -3.700Result French victory[1]Belligerents French Empire United Kingdom Portugal Spain Commanders and leaders Jean-Louis Dubreton Arthur WellesleyStrength 2,000[1] 3…
Halaman ini berisi artikel tentang bagian pembacaan di seluruh Tanakh. Untuk bacaan mingguan (Parashat HaShavua), lihat Bacaan Taurat Mingguan. Sebuah halaman dari Kodeks Aleppo yang memuat Ulangan 32:50-33:29. Pemisahan parsyah pada halaman ini adalah: {P} 33:1-6 (kolom kanan, baris kosong, baris ke-8 dari atas) {S} 33:7 (kolom kanan, baris berindentasi, baris ke-23) {P} 33:8-11 (kolom kanan, baris kosong, baris ke-2 dari bawah) {S} 33:12 (kolom tengah, indentasi pertama) {S} 33:13-17 (kolom te…
« CD » redirige ici. Pour les autres significations, voir CD (homonymie). Disque compact Type de média Disque optique Capacité 0,21 à 0,91 Go, la plupart du temps 0,74 Go Mécanisme de lecture Diode laser de longueur d'onde de 780 nm Développé par Philips, Sony Dimensions physiques Ø 12 cm / 8 cm Utilisé pour lecteurs CD, chaînes hi-fi, ordinateurs, consoles de jeux vidéo modifier Un disque compact, le plus souvent désigné par son sigle anglais CD – …
Flag carrier of the Philippines This article is about the airline based in the Philippines. For a full list of all active Philippine-based airlines, see List of airlines of the Philippines. Not to be confused with PAL Airlines or PAL Airlines (Chile). Philippine Airlines IATA ICAO Callsign PR PAL PHILIPPINE FoundedFebruary 26, 1941; 83 years ago (1941-02-26)(as Philippine Air Lines)[a]Commenced operationsMarch 15, 1941; 83 years ago (1941-03-15)AOC…
David ThewlisThewlis pada tahun 2008LahirDavid Thewlis20 Maret 1963 (umur 61)Blackpool, InggrisPekerjaanAktor, Sutradara, Penulis skenario, PengarangTahun aktif1985-sekarangSuami/istriSara Sugarman (m. 1992; c. 1994)PasanganAnna Friel(2001–2010)Anak1 David Wheeler (lahir 20 Maret 1963), dikenal secara profesional sebagai David Thewlis (/ˈθjuːlɪs/), adalah seorang aktor Inggris, sutradara, penulis skenario, dan Pengarang. Thewlis…
Overview of secularism in Albania This article is part of a series inCulture ofAlbania History Illyrians Middle Ages Ottoman period Independent Albania People Albanians Clans Noble families Diaspora Language Gheg Arbanasi (Dalmatia) Upper Reka dialect Istrian Albanian Tosk Lab Cham Arvanitika Arvanitic Arbëresh Tradition Besa Kanun Oda Sworn virgins Costumes Religion and folklore Islam Christianity Judaism Irreligion Secularism Folk beliefs Art Art galleries Architecture Cuisine Albanian cuisin…
Wilhelm von Edelsheim ritratto da Raphael Mengs Wilhelm von Edelsheim (Hanau, 13 novembre 1737 – Karlsruhe, 6 dicembre 1793) è stato un politico e diplomatico tedesco. Fu presidente del consiglio privato e primo ministro del Margraviato del Baden. Biografia Wilhelm von Edelsheim era membro di una famiglia aristocratica tedesca originaria di Hanau, dove egli stesso nacque. Suo padre, Philipp Reinhard von Edelsheim (27 luglio 1695 - 11 luglio 1772), era primo ministro della contea di Hanau-Munz…
Batgirl and the Birds of PreyTextless artwork for issue #22, art by Terry Dodson and Rachel Dodson.Publication informationPublisherDC ComicsScheduleMonthlyFormatOngoing seriesGenre Superhero Publication dateSeptember 2016 – July 2018No. of issues22 + Rebirth one-shotMain character(s)BatgirlBlack CanaryHuntressCreative teamWritten byJulie BensonShawna BensonPenciller(s) List Rebirth #1; #1–3, 7Claire Roe#4–6, 8–13, 15, 19–22Roge Antonio#14, 16–18Marcio Takara Inker(s) L…