NUMAL Section 2.2.1.1

BEGIN SECTION : 2.2.1.1 (October, 1975)

AUTHOR: C.G. VAN DER LAAN.

INSTITUTE: REKENCENTRUM RIJKSUNIVERSITEIT GRONINGEN.

RECEIVED: 741114.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS THE PROCEDURES POL, TAYPOL, NORDERPOL AND
    DERPOL.

    POL EVALUATES A POLYNOMIAL;

    DERPOL EVALUATES THE FIRST K DERIVATIVES OF A POLYNOMIAL;

    NORDERPOL EVALUATES THE FIRST K NORMALIZED DERIVATIVES OF A
    POLYNOMIAL (I.E. J-TH DERIVATIVE/(J FACTORIAL),J=0,1,...,K<=DEGREE;

    TAYPOL EVALUATES X**J*(J-TH DERIVATIVE)/(J FACTORIAL),
    J=0,1,...,K<=DEGREE.

KEYWORDS:

    POLYNOMIAL EVALUATION,
    (NORMALIZED) DERIVATIVES,
    DERIVATIVES OF A POLYNOMIAL.


SUBSECTION: POL.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE" POL(N,X,A);
    "VALUE"N,X;"INTEGER"N;"REAL"X;"ARRAY"A;
    "CODE" 31040;

    POL:=A[0]+A[1]*X+...+A[N]*X**N;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE DEGREE OF THE POLYNOMIAL;
    X:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
    A:   <ARRAY IDENTIFIER>;
         "ARRAY"A[0:N];
         ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
                A[0]+A[1]*X+...+A[N]*X**N.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (N MULTIPLICATIONS AND ADDITIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:
    THE METHOD USED FOR EVALUATION IS HORNER'S RULE (SYNTHETIC
    DIVISION). THE ERROR GROWTH IS GIVEN BY A LINEAR FUNCTION OF THE
    DEGREE OF THE POLYNOMIAL (SEE VAN DER LAAN, STOER(1972) P. 29 (EX.
    11) OR WILKINSON(1963) P. 36,37).


SUBSECTION: DERPOL.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE" DERPOL(N,K,X,A);
    "VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
    "CODE" 31243;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE DEGREE OF THE POLYNOMIAL;
    K:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE FIRST K DERIVATIVES ARE TO BE CALCULATED;
    X:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
    A:   <ARRAY IDENTIFIER>;
         "ARRAY"A[0:N];
         ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
                A[0]+A[1]*X+...+A[N]*X**N;
         EXIT: THE J-TH DERIVATIVE IS DELIVERED IN A[J], J=0,1,...,K<=
               DEGREE; THE OTHER ELEMENTS ARE GENERALLY ALTERED.

PROCEDURES USED :

     NORDERPOL  =  CP31242

RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
              THE NUMBER OF MULTIPLICATIONS IS N, IN FIRST ORDER.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE: SEE TAYPOL(THIS SECTION).


SUBSECTION: NORDERPOL.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:

    "PROCEDURE" NORDERPOL(N,K,X,A);
    "VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
    "CODE" 31242;

    THE MEANING OF THE FORMAL PARAMETERS IS:

    N:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE DEGREE OF THE POLYNOMIAL;
    K:   <ARITHMETIC EXPRESSION>;
         THE FIRST K NORMALIZED DERIVATIVES ARE TO BE CALCULATED
         (I.E. (J-TH DERIVATIVE)/(J FACTORIAL), J=0,1,...,K<=DEGREE).
    X:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
    A:   <ARRAY IDENTIFIER>;
         "ARRAY"A[0:N];
         ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
                A[0]+A[1]*X+...+A[N]*X**N;
         EXIT: THE J-TH NORMALIZED DERIVATIVE IS DELIVERED IN A[J]
               J=0,1,...,K<=DEGREE; THE OTHER ELEMENTS ARE GENERALLY
               ALTERED.

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY: AN AUXILIARY ARRAY OF ORDER N + 1 IS DECLARED.

RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
              THE NUMBER OF MULTIPLICATIONS/DIVISIONS IS 2 * N + K.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE: SEE TAYPOL(THIS SECTION).


SUBSECTION: TAYPOL.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:

    "PROCEDURE" TAYPOL(N,K,X,A);
    "VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
    "CODE" 31241;

    THE MEANING OF THE FORMAL PARAMETERS IS:

    N:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE DEGREE OF THE POLYNOMIAL;
    K:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE FIRST K TERMS X**J*(J-TH DERIVATIVE)/(J FACTORIAL),
                J=0,1,...,K<=DEGREE, ARE TO BE CALCULATED;
    X:   <ARITHMETIC EXPRESSION>;
         ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
    A:   <ARRAY IDENTIFIER>;
         "ARRAY"A[0:N];
         ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
                A[0]+A[1]*X+...+A[N]*X**N;
         EXIT: THE J-TH TERM X**J*(J-TH DERIVATIVE)/(J FACTORIAL), IS
               DELIVERED IN A[J], J=0,1,...,K<=DEGREE; THE OTHER
               ELEMENTS ARE GENERALLY ALTERED.

PROCEDURES USED: NONE.

RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
              THE NUMBER OF MULTIPLICATIONS IS 2 * N.

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE:
    THE METHOD OF EVALUATION IS GIVEN BY TRAUB AND SHAW(1972,1974).
    LET X**J*(J-TH DERIVATIVE OF THE POLYNOMIAL)/(J FACTORIAL)=
    (J OVER J)*A[J]*X**J+(J+1 OVER J)*A[J+1]*X**(J+1)+...+(N OVER J)*
    A[N]*X**N,THEN THE J-TH DERIVATIVE (UP TO A FACTOR) CAN BE OBTAINED
    FROM THE BINOMIAL COEFFICIENTS FOLLOWED BY EVALUATION OF THE ABOVE
    INPRODUCT. THE SHAW AND TRAUB ALGORITHM PERFORMS THE BUILDING UP OF
    THE BINOMIAL COEFFICIENTS IMPLICITLY.
    WE HAVE NOT IMPLEMENTED THE MORE SOPHISTICATED ALGORITHM, BASED
    ON DIVISORS OF N+1, BECAUSE OF THE MORE COMPLEX APPEARANCE
    OF  THE IMPLEMENTATION AND BECAUSE OF THE DIFFICULTY IN CHOSING
    THE MOST EFFICIENT DIVISOR. OUR (RESTRICTED) IMPLEMENTATION OF THE
    ONE-PARAMETER FAMILY OF ALGORITHMS PRESERVES THE LINEAR NUMBER OF
    MULTIPLICATIONS (2*N (NORDERPOL, TAYPOL) AND 3*N (DERPOL)).
    THE ABSOLUTE ERROR IS OF ORDER MAX((N OVER N)*A[N]*X**(N-K),...,
    (N OVER K)*A[K]), FOR THE K-TH NORMALIZED DERIVATIVE (SEE VAN DER
    LAAN OR WOZNIAKOWSKI).

REFERENCES:

    [1].SHAW,M. AND J. TRAUB:
        ON THE NUMBER OF MULTIPLICATIONS FOR THE EVALUATION OF A
        POLYNOMIAL AND SOME OF ITS DERIVATIVES (21 P.).
        JOURN. ACM, 1974, VOL. 21, NO. 1, P. 161-167.

    [2].STOER,J. :
        EINFUEHRUNG IN DIE NUMERISCHE MATHEMATIK 1.
        SPRINGER, 1972.

    [3].VAN DER LAAN C.G.:
        ORTHOGONAL POLYNOMIALS IN NUMERICAL ANALYSIS.
        1. ERROR ANALYSIS OF RECURRENCE RELATIONS IN FLOATING-POINT
        COMPUTATION, (TO APPEAR).

    [4].WILKINSON,J.H. :
        ROUNDING ERRORS IN ALGEBRAIC PROCESSES.
        HSO, NOTES ON APPLIED SCIENCES NO. 32, 1963.

    [5].WOZNIAKOWSKI,H.:
        ROUNDING ERROR ANALYSIS FOR THE EVALUATION OF A POLYNOMIAL AND
        SOME OF ITS DERIVATIVES.
        SIAM J. OF NUM. AN. VOL 11, NO. 4, P. 780-787.

EXAMPLE OF USE:

    AS A FORMAL TEST OF THE PROCEDURE DERPOL THE DERIVATIVES OF THE
    POLYNOMIAL 3*X**3-2*X**2+X-1 ARE CALCULATED AT X=1.

    "BEGIN""ARRAY"A[0:3];
         A[3]:=3;A[2]:=-2;A[1]:=1;A[0]:=-1;
         DERPOL(3,3,1,A); OUTPUT(61,"("
         "("THE 0-TH UNTIL AND INCLUDING THE 3-TH DERIVATIVES :")",
         4(BZDB)")",A[0],A[1],A[2],A[3]);
    "END" EXAMPLE OF USE;

    THE 0-TH UNTIL AND INCLUDING THE 3-TH DERIVATIVES :  1  6  14  18

SOURCE TEXT(S):
"CODE" 31040;
"CODE" 31241;
"CODE" 31242;
"CODE" 31243;