PROBLEM
We wish to perform calculations such as

(2 + 3*X + 6*X**2) + (2 - X**2) = (4 + 3*X + 5*X**2)

When polynomials are represented by the arrays, then following procedure is a straightforward implementation of polynomial addition:

IMPLEMENTATION
Unit: nonrecursive internal subroutine

Global variables: an array A. of N+1 coefficients, an array B. of N+1 coefficients.

Parameter: a positive integer N - a degree of the A. and B. polynomials.

Result: The A. array includes coefficients of polynomial addition.

 POLYADD: procedure expose A. B. parse arg N do J = 0 to N; A.J = A.J + B.J; end return

EXAMPLE
(12*X**54 + 65*X**80 + 3*X*10000) +
(3*X**12 - 13*X**54 + 13*X**98 + 7*X**10000) =
3*X**12 - X**54 + 65*X*80 + 13*X*98 + 10*X**10000

 N = 10000 A. = 0; A.54 = 12; A.80 = 65; A.10000 = 3 B. = 0; B.12 = 3; B.54 = -13 B.98 = 13; B.10000 = 7 call POLYADD N do I = 1 to N   if A.I <> 0 then say I A.I end exit POLYADD: procedure expose A. B. ...

displays on the screen

 12 3 54 -1 80 65 98 13 10000 10

SPARSE POLYNOMIALS
For processing "sparse" polynomials with many zero coefficients, we can have array nodes represent only the nonzero terms. A sparse polynomial

A.N*X**N+...+A.J*X**J+...+A.1*X+A.0

can be represented by an ascending sequence of pairs J A.J only for nonzero coefficients A.J.

IMPLEMENTATION
Unit: nonrecursive internal subroutine

Global variables: an ascending sequence A. of M couples coefficient power, an ascending sequence B. of N couples coefficient power, and an output array C. as result of polynomial addition

Parameters: positive integers M, N - size of the A. and B. arrays.

Result: Returns size of the C. array. The C. array includes couples represent of polynomial addition.

 SPARSE_POLYADD: procedure expose A. B. C. parse arg M, N K = 1; L = 1; J = 0 do while K <= M & L <= N   parse var A.K Apower Acoef   parse var B.L Bpower Bcoef   select     when Apower < Bpower       then do; J = J + 1; C.J = A.K; K = K + 1; end     when Apower > Bpower       then do; J = J + 1; C.J = B.L; L = L + 1; end     otherwise       Sum = Acoef + Bcoef       if Sum <> 0         then do; J = J + 1; C.J = Apower Sum; end       K = K + 1; L = L + 1   end end do while K <= M; J = J + 1; C.J = A.K; K = K + 1; end do while L <= N; J = J + 1; C.J = B.L; L = L + 1; end return J

EXAMPLE
The following fragment of program

 M = 3 A.1 = 54 12; A.2 = 80 65; A.3 = 10000 3 N = 4 B.1 = 12 3; B.2 = 54 "-13"; B.3 = 98 13 B.4 = 10000 7 J = SPARSE_POLYADD(M, N) do I = 1 to J; say C.I; end exit SPARSE_POLYADD: procedure expose A. B. C. ...

displays on the screen

 12 3 54 -1 80 65 98 13 10000 10

CONNECTIONS

 cover contents index main page