Horner's rule
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, Horner's method (or Horner's scheme) is an algorithm for
polynomial evaluation In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial P(x_1, x_2) = 2x_1x_2 + x_1^3 + 4 at ...
. Although named after
William George Horner William George Horner (9 June 1786 – 22 September 1837) was a British mathematician. Proficient in classics; mathematics, he was a schoolmaster, headmaster and schoolkeeper, who wrote extensively on functional equations, number theory and app ...
, this method is much older, as it has been attributed to
Joseph-Louis Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiapolynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
of degree with only n multiplications and n additions. This is optimal, since there are polynomials of degree that cannot be evaluated with fewer arithmetic operations. 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 In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-va ...
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 :p(x) = \sum_^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n, where a_0, \ldots, a_n are constant coefficients, the problem is to evaluate the polynomial at a specific value x_0 of x. For this, a new sequence of constants is defined
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
as follows: :\begin b_n & := a_n \\ b_ & := a_ + b_n x_0 \\ (1)\quad\quad\quad & ~~~ \vdots \\ b_1 & := a_1 + b_2 x_0 \\ b_0 & := a_0 + b_1 x_0. \end Then b_0 is the value of p(x_0). To see why this works, the polynomial can be written in the form :p(x) = a_0 + x \bigg(a_1 + x \Big(a_2 + x \big(a_3 + \cdots + x(a_ + x \, a_n) \cdots \big) \Big) \bigg) \ . Thus, by iteratively substituting the b_i into the expression, : \begin p(x_0) & = a_0 + x_0\Big(a_1 + x_0\big(a_2 + \cdots + x_0(a_ + b_n x_0) \cdots \big)\Big) \\ & = a_0 + x_0\Big(a_1 + x_0\big(a_2 + \cdots + x_0 b_\big)\Big) \\ & ~~ \vdots \\ & = a_0 + x_0 b_1 \\ & = b_0. \end Now, it can be proven that; : (2)\quad\quad\quad p(x) = (b_1 + b_2 x + b_3 x^2 + b_4x^3 + \cdots + b_ x^ +b_nx^)(x-x_0)+b_0 This expression constitutes Horner's practical application, as it offers a very quick way of determining the outcome of; : p(x)/(x-x_0) with b0 (which is equal to p(x0)) being the division's remainder, as is demonstrated by the examples below. if x0 is a root of p(x), then b0 = 0 (meaning the remainder is 0), which means you can factor p(x) with (x-x0).
As to finding the consecutive b-values, you start with determining bn, which is simply equal to an. You then work your way down to the other b's, using the formula; : b_=a_+b_x_0 till you arrive at b0.


Examples

Evaluate f(x)=2x^3-6x^2+2x-1 for x=3. We use synthetic division as follows: ''x0''│ ''x3'' ''x2'' ''x1'' ''x0'' 3 │ 2 −6 2 −1 │ 6 0 6 └──────────────────────── 2 0 2 5 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 f(x) on division by x-3 is 5. But by the
polynomial remainder theorem In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
, we know that the remainder is f(3) . Thus f(3) = 5 In this example, if a_3 = 2, a_2 = -6, a_1 = 2, a_0 = -1 we can see that b_3 = 2, b_2 = 0, b_1 = 2, b_0 = 5 , the entries in the third row. So, synthetic division is based on 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 f(x) on division by x-3 . The remainder is 5. This makes Horner's method useful for
polynomial long division In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, bec ...
. Divide x^3-6x^2+11x-6 by x-2: 2 │ 1 −6 11 −6 │ 2 −8 6 └──────────────────────── 1 −4 3 0 The quotient is x^2-4x+3. Let f_1(x)=4x^4-6x^3+3x-5 and f_2(x)=2x-1. Divide f_1(x) by f_2\,(x) using Horner's method. 0.5 │ 4 -6 0 3 -5 │ 2 -2 -1 1 └─────────────────────── 2 -2 -1 1 -4 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 :\frac=2x^3-2x^2-x+1-\frac.


Efficiency

Evaluation using the monomial form of a degree-''n'' polynomial requires at most ''n'' additions and (''n''2 + ''n'')/2 multiplications, if powers are calculated by repeated multiplication and each monomial is evaluated individually. (This can be reduced to ''n'' additions and 2''n'' − 1 multiplications by evaluating the powers of ''x'' iteratively.) If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately 2''n'' times the number of bits of ''x'' (the evaluated polynomial has approximate magnitude ''xn'', and one must also store ''xn'' itself). By contrast, Horner's method requires only ''n'' additions and ''n'' multiplications, and its storage requirements are only ''n'' times the number of bits of ''x''. Alternatively, Horner's method can be computed with ''n''
fused multiply–add Fuse or FUSE may refer to: Devices * Fuse (electrical), a device used in electrical systems to protect against excessive current ** Fuse (automotive), a class of fuses for vehicles * Fuse (hydraulic), a device used in hydraulic systems to prot ...
s. Horner's method can also be extended to evaluate the first ''k'' derivatives of the polynomial with ''kn'' additions and multiplications. 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 Alexander Markowich Ostrowski ( uk, Олександр Маркович Островський; russian: Алекса́ндр Ма́ркович Остро́вский; 25 September 1893, in Kiev, Russian Empire – 20 November 1986, in Mont ...
proved in 1954 that the number of additions required is minimal. Victor Pan proved in 1966 that the number of multiplications is minimal. However, when ''x'' 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-''n'' polynomial can be evaluated using only +2 multiplications and ''n'' additions.


Parallel evaluation

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: :\begin p(x) & = \sum_^n a_i x^i \\ & = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n \\ & = \left( a_0 + a_2 x^2 + a_4 x^4 + \cdots\right) + \left(a_1 x + a_3 x^3 + a_5 x^5 + \cdots \right) \\ & = \left( a_0 + a_2 x^2 + a_4 x^4 + \cdots\right) + x \left(a_1 + a_3 x^2 + a_5 x^4 + \cdots \right) \\ & = \sum_^ a_ x^ + x \sum_^ a_ x^ \\ & = p_0(x^2) + x p_1(x^2). \\ \end More generally, the summation can be broken into ''k'' parts: :\begin p(x) & = \sum_^n a_i x^i \\ & = \sum_^ x^j \sum_^ a_ x^ \\ & = \sum_^ x^j p_j(x^k) \\ \end 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 Single instruction, multiple data (SIMD) is a type of parallel processing in Flynn's taxonomy. SIMD can be internal (part of the hardware design) and it can be directly accessible through an instruction set architecture (ISA), but it shoul ...
execution of most of them. Modern compilers generally evaluate polynomials this way when advantageous, although for
floating-point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can ...
calculations this requires enabling (unsafe) reassociative math.


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 A microcontroller (MCU for ''microcontroller unit'', often also MC, UC, or μC) is a small computer on a single VLSI integrated circuit (IC) chip. A microcontroller contains one or more CPUs ( processor cores) along with memory and programmabl ...
with no
hardware multiplier A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve comp ...
. One of the binary numbers to be multiplied is represented as a trivial polynomial, where (using the above notation) a_i = 1, and x = 2. Then, ''x'' (or ''x'' to some power) is repeatedly factored out. In this
binary numeral system A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one). The base-2 numeral system is a positional notati ...
(base 2), x = 2, so powers of 2 are repeatedly factored out.


Example

For example, to find the product of two numbers (0.15625) and ''m'': : \begin (0.15625) m & = (0.00101_b) m = ( 2^ + 2^) m = (2^)m + (2^)m \\ & = 2^ (m + (2^)m) = 2^ (m + 2^ (m)). \end


Method

To find the product of two binary numbers ''d'' and ''m'': :1. A register holding the intermediate result is initialized to ''d''. :2. Begin with the least significant (rightmost) non-zero bit in ''m''. ::2b. 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. ::2c. Using that value, perform a left-shift operation by that number of bits on the register holding the intermediate result :3. 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 ( d_3 d_2 d_1 d_0 ) the product is : (d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0)m = d_3 2^3 m + d_2 2^2 m + d_1 2^1 m + d_0 2^0 m. 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 In mathematics, division by zero is division where the divisor (denominator) is zero. Such a division can be formally expressed as \tfrac, where is the dividend (numerator). In ordinary arithmetic, the expression has no meaning, as there is ...
is not an issue, despite this implication in the factored equation: : = d_0\left(m + 2 \frac \left(m + 2 \frac \left(m + 2 \frac (m)\right)\right)\right). The denominators all equal one (or the term is absent), so this reduces to : = d_0(m + 2 (m + 2 (m + 2 (m)))), or equivalently (as consistent with the "method" described above) : = d_3(m + 2^ (m + 2^ (m + (m)))). 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 In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. For binary ...
. The factor (2−1) is a right
arithmetic shift In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. For binary ...
, a (0) results in no operation (since 20 = 1 is the multiplicative
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
), 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 The non-adjacent form (NAF) of a number is a unique signed-digit representation, in which non-zero values cannot be adjacent. For example: :(0 1 1 1)2 = 4 + 2 + 1 = 7 :(1 0 −1 1)2 = 8 − 2 + 1 = 7 :(1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7 :(1 0 0 ...
" (CSD) form is used) and uses only 20% of the code space.


Other applications

Horner's method can be used to convert between different positional
numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbo ...
s – in which case ''x'' is the base of the number system, and the ''a''''i'' coefficients are the digits of the base-''x'' representation of a given number – and can also be used if ''x'' is a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
, in which case the gain in computational efficiency is even greater. However, for such cases faster methods are known.


Polynomial root finding

Using the long division algorithm in combination with
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real- ...
, it is possible to approximate the real roots of a polynomial. The algorithm works as follows. Given a polynomial p_n(x) of degree n with zeros z_n < z_ < \cdots < z_1, make some initial guess x_0 such that z_1 < x_0 . Now iterate the following two steps: # Using
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real- ...
, find the largest zero z_1 of p_n(x) using the guess x_0. # Using Horner's method, divide out (x-z_1) to obtain p_. Return to step 1 but use the polynomial p_ and the initial guess z_1. 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.


Example

Consider the polynomial : p_6(x) = (x+8)(x+5)(x+3)(x-2)(x-3)(x-7) which can be expanded to : p_6(x) = x^6 + 4x^5 - 72x^4 -214x^3 + 1127x^2 + 1602x -5040. 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 p(x) is divided by (x-7) to obtain : p_5(x) = x^5 + 11x^4 + 5x^3 - 179x^2 - 126x + 720 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 (x-3) to obtain : p_4(x) = x^4 + 14x^3 + 47x^2 - 38x - 240 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 : p_3(x) = x^3 + 16x^2 + 79x + 120 which is shown in green and found to have a zero at −3. This polynomial is further reduced to : p_2(x) = x^2 + 13x + 40 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 p_2(x) and solving the
linear equation In mathematics, a linear equation is an equation that may be put in the form a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coeffici ...
. 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 (p(y) - p(x))/(y - x). Given the polynomial (as before) :p(x) = \sum_^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n, proceed as follows :\begin b_n & = a_n, &\quad d_n &= b_n, \\ b_ & = a_ + b_n x, &\quad d_ &= b_ + d_n y, \\ & \ \ \vdots &\quad & \ \ \vdots\\ b_1 & = a_1 + b_2 x, &\quad d_1 &= b_1 + d_2 y,\\ b_0 & = a_0 + b_1 x. \end At completion, we have :\begin p(x) &= b_0, \\ \frac &= d_1, \\ p(y) &= b_0 + (y - x) d_1. \end This computation of the divided difference is subject to less round-off error than evaluating p(x) and p(y) separately, particularly when x \approx y. Substituting y = x in this method gives d_1 = p'(x), the derivative of p(x).


History

Horner's paper, titled "A new method of solving numerical equations of all orders, by continuous approximation",. wa
read
before the Royal Society of London, at its meeting on July 1, 1819, with a sequel in 1823. Horner's paper in Part II of ''Philosophical Transactions of the Royal Society of London'' for 1819 was warmly and expansively welcomed by
reviewer
in the issue of ''The Monthly Review: or, Literary Journal'' for April, 1820; in comparison, a technical paper by
Charles Babbage Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer. Babbage is considered ...
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 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: * Paolo Ruffini in 1809 (see Ruffini's rule). *
Isaac Newton Sir Isaac Newton (25 December 1642 – 20 March 1726/27) was an English mathematician, physicist, astronomer, alchemist, Theology, theologian, and author (described in his time as a "natural philosophy, natural philosopher"), widely ...
in 1669 * the Chinese mathematician
Zhu Shijie Zhu Shijie (, 1249–1314), courtesy name Hanqing (), pseudonym Songting (), was a Chinese mathematician and writer. He was a Chinese mathematician during the Yuan Dynasty. Zhu was born close to today's Beijing. Two of his mathematical works ha ...
in the 14th century * the Chinese mathematician
Qin Jiushao Qin Jiushao (, ca. 1202–1261), courtesy name Daogu (道古), was a Chinese mathematician, meteorologist, inventor, politician, and writer. He is credited for discovering Horner's method as well as inventing Tianchi basins, a type of rain gau ...
in his ''
Mathematical Treatise in Nine Sections The ''Mathematical Treatise in Nine Sections'' () is a mathematical text written by Chinese Southern Song dynasty mathematician Qin Jiushao in the year 1247. The mathematical text has a wide range of topics and is taken from all aspects of th ...
'' in the 13th century * the Persian
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...
Sharaf al-Dīn al-Ṭūsī in the 12th century (the first to use that method in a general case of cubic equation) * the Chinese mathematician
Jia Xian Jia Xian (; ca. 1010–1070) was a Chinese mathematician from Kaifeng of the Song dynasty. Biography According to the history of the Song dynasty, Jia was a palace eunuch of the Left Duty Group. He studied under the mathematician Chu Yan, and ...
in the 11th century (
Song dynasty The Song dynasty (; ; 960–1279) was an imperial dynasty of China that began in 960 and lasted until 1279. The dynasty was founded by Emperor Taizu of Song following his usurpation of the throne of the Later Zhou. The Song conquered the res ...
) * ''
The Nine Chapters on the Mathematical Art ''The Nine Chapters on the Mathematical Art'' () is a Chinese mathematics book, composed by several generations of scholars from the 10th–2nd century BCE, its latest stage being from the 2nd century CE. This book is one of the earliest sur ...
'', a Chinese work of the
Han dynasty The Han dynasty (, ; ) was an Dynasties in Chinese history, imperial dynasty of China (202 BC – 9 AD, 25–220 AD), established by Emperor Gaozu of Han, Liu Bang (Emperor Gao) and ruled by the House of Liu. The dynasty was preceded by th ...
(202 BC – 220 AD) edited by
Liu Hui Liu Hui () was a Chinese mathematician who published a commentary in 263 CE on ''Jiu Zhang Suan Shu ( The Nine Chapters on the Mathematical Art).'' He was a descendant of the Marquis of Zixiang of the Eastern Han dynasty and lived in the state ...
(fl. 3rd century).
Qin Jiushao Qin Jiushao (, ca. 1202–1261), courtesy name Daogu (道古), was a Chinese mathematician, meteorologist, inventor, politician, and writer. He is credited for discovering Horner's method as well as inventing Tianchi basins, a type of rain gau ...
, in his ''Shu Shu Jiu Zhang'' (''
Mathematical Treatise in Nine Sections The ''Mathematical Treatise in Nine Sections'' () is a mathematical text written by Chinese Southern Song dynasty mathematician Qin Jiushao in the year 1247. The mathematical text has a wide range of topics and is taken from all aspects of th ...
''; 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 Jia Xian (; ca. 1010–1070) was a Chinese mathematician from Kaifeng of the Song dynasty. Biography According to the history of the Song dynasty, Jia was a palace eunuch of the Left Duty Group. He studied under the mathematician Chu Yan, and ...
; 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:
Ulrich Libbrecht Ulrich Libbrecht (10 July 1928, Avelgem – 15 May 2017) was a Belgian philosopher and author in the field of comparative philosophy. His magnum opus consists of four books in Dutch - called "Introduction to Comparative Philosophy". An abbrev ...
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.. The extraction of square and cube roots along similar lines is already discussed by
Liu Hui Liu Hui () was a Chinese mathematician who published a commentary in 263 CE on ''Jiu Zhang Suan Shu ( The Nine Chapters on the Mathematical Art).'' He was a descendant of the Marquis of Zixiang of the Eastern Han dynasty and lived in the state ...
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.


See also

*
Clenshaw algorithm In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials. Note that this paper is written in terms of the ''Shifted'' Chebyshev polynomials of the ...
to evaluate polynomials in Chebyshev form *
De Boor's algorithm In the mathematical subfield of numerical analysis de Boor's algorithmC. de Boor 971 "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121. is a polynomial-time and numerically s ...
to evaluate splines in
B-spline In the mathematical subfield of numerical analysis, a B-spline or basis spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expresse ...
form *
De Casteljau's algorithm In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to s ...
to evaluate polynomials in Bézier form * Estrin's scheme to facilitate parallelization on modern computer architectures * Lill's method to approximate roots graphically * Ruffini's rule and synthetic division to divide a polynomial by a binomial of the form x − r


Notes


References

* * Read before the Southwestern Section of the American Mathematical Society on November 26, 1910. * * * * * *: Holdred's method is in the supplement following page numbered 45 (which is the 52nd page of the pdf version). * *: 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. * * * * * * * * * * * * *: Reprinted from issues of ''The North China Herald'' (1852).


External links

* * Qiu Jin-Shao
Shu Shu Jiu Zhang
(Cong Shu Ji Cheng ed.) * For more on the root-finding application se

{{Polynomials Algebra Polynomials Numerical analysis