This is a sub-page of a longer article, The classical Chinese version of Horner’s method: Technical considerations.

Appendix 4
Computer program to illustrate classical
Chinese root extraction:
The general case

100 ' Initialization

110 '

120 epsilon = 0.01

130 root = 0

140 mat origin 0

150 thisisfirsttry = 1

160 rootlowerlimit = 1.000000E-03

170 '

180 ' Ask for the coefficients of the polynomial

190 '

200 input "highest exponent: ", n

210 dim coeff(n)

220 print "coefficients:"

230 for i = n to 0 step -1

240     input coeff(i)

250     next i

260 '

270 ' Ask for a digit value which is larger than the value of the first digit.

280 '

290 input "first try: ", ceiling

300 order = 10^(floor(log10(ceiling)))

310 d = floor(ceiling/order)

320 '

330 ' Subroutine to reduce the roots of the equation by the value of the first digit.

340 '

350 sub chu(dv)

360     for m = 0 to n-1

370         for i = n-1 to m step -1

380             coeff(i) = coeff(i)+dv*coeff(i+1)

390             next i

400         next m

410     end sub

420 '

430 ' Reduce the roots

440 '

450 chu(d*order)

460 '

470 ' If this is the first try, determine the first sign of the constant coefficient.

480 '

490 if thisisfirsttry = 1 then

500     constsign = sgn(coeff(0))

510     thisisfirsttry = 0

520     endif

530 '

540 ' If the desired precision has been reached, accept this root and exit.

550 '

560 if abs(coeff(0)) < epsilon then

570     root = root+d*order

580     goto 950

590     endif

600 '

610 ' If the accumulated root is too small, report that there is no root and exit.

620 '

630 if root+d*order < rootlowerlimit then

640     print "No root less than ",ceiling

650     goto 960

660     endif

670 '

680 ' Otherwise, if the constant term has not changed sign, the digit is too large.

690 ' Undo the previous action, propose a smaller digit, and try again.

700 '

710 if sgn(coeff(0)) = constsign then

720     chu(-d*order)

730     d = d-1

740     if d = 0 then

750         d = 9

760         order = order/10

770         endif

780     goto 450

790     endif

800 '

810 ' Add the value of the digit to the accumulated result.

820 '

830 root = root+d*order

840 '

850 ' If the desired precision has not been reached, propose the next digit.

860 '

870 if abs(coeff(0)) > epsilon then

880      d = 9

890     order = order/10

900     goto 450

910     endif

920 '

930 ' Print the final result and exit.

940 '

950 print "root=", root

960 end