Current location - Training Enrollment Network - Mathematics courses - Qin's algorithm topic
Qin's algorithm topic
Qin algorithm is a polynomial simplification algorithm proposed by Qin, a mathematician in the Southern Song Dynasty. Known as Horner algorithm or Horner scheme in the west, it is named after the British mathematician William George Horner.

Rewrite a polynomial f (x) = a [n] x n+a [n-1] x (n-1)+. +a [1] x+a [0] becomes the following form:

f(x)=a[n]x^n+a[n- 1]x^(n- 1))+.+a[ 1]x+a[0]

=(a[n]x^(n- 1)+a[n- 1]x^(n-2)+.+a[ 1])x+a[0]

=((a[n]x^(n-2)+a[n- 1]x^(n-3)+.+a[2])x+a[ 1])x+a[0]

=.

=(.((a[n]x+a[n- 1])x+a[n-2])x+。 +a[ 1])x+a[0]。

To calculate the value of a polynomial, first calculate the value of the polynomial in the innermost bracket, that is

v[ 1]=a[n]x+a[n- 1]

Then the value of the polynomial is calculated layer by layer from the inside out, that is

v[2]=v[ 1]x+a[n-2]

v[3]=v[2]x+a[n-3]

.

v[n]=v[n- 1]x+a[0]

In this way, finding the value of n-degree polynomial f(x) is transformed into finding the value of n-degree polynomial.

(Note: Numbers in brackets indicate subscripts)

Conclusion: For polynomial of degree n, the maximum is multiplication and addition.

Alternative calculation:

v[ 1]= a[n]x+a[n- 1]= 4 *(2)+3 =-5

v[2]=(-5)*(-2)+2= 12

v[3]= 12 *(2)- 1 =-25

v[4]=(-25)*(-2)- 1=49

V[5]= 49 *(2)- 1/2 =-98 and 1/2.

Find the polynomial f (x) = 4x5+3x4+2x3-x2-x-21by Qin algorithm. When x=-2, the values are (-98 and 1/2).