Division of polynomials

PROBLEM
Given the N+1 coefficients of a polynomial of degree N in A.0,A.1,...,A.N, and M+1 coefficients of a polynomial of degree M in B.0,B.1,...,B.M, divide the polynomial A. by the polynomial B. giving a quotient polynomial in Q.1,Q.2,...,Q.NmM, where NmM=N-M and remainder polynomial whose coefficients are in R.1,R.2,...,R.Mm1, where Mm1=M-1.

IMPLEMENTATION
Unit: internal subroutine

Global variables: input arrays A., B.; output arrays Q., R.

Parameters: positive integers N, M; N>=M>=0

Result: quotient polynomial in Q.1,Q.2,...,Q.NmM, where NmM=N-M; remainder polynomial in R.1,R.2,...,R.Mm1, where Mm1=M-1

 POLDIV: procedure expose A. B. R. Q. parse arg N, M Q. = 0 do J = 0 to N; R.J = A.J; end do K = N - M to 0 by -1   MpK = M + K; Q.K = R.MpK / B.M   do J = M + K - 1 to K by -1     JmK = J - K; R.J = R.J - Q.K * B.JmK   end end return

EXAMPLE
The following program

 N = 4; M = 2 A.0 = 6; A.1 = -5; A.2 = 4; A.3 = -3; A.4 = 2 B.0 = 1; B.1 = -3; B.2 = 1 call POLDIV N, M Quo = "" do J = N - M to 0 by -1; Quo = Quo Q.J"*X**"J; end Rem = "" do J = M - 1 to 0 by -1; Rem = Rem R.J"*X**"J; end say "quotient" Quo || "; remainder" Rem exit POLDIV: procedure expose A. B. R. Q. ...

displays on the screen

quotient 2*X**2 3*X**1 11*X**0; remainder 25*X**1 -5*X**0

CONNECTIONS

Literature
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in C : the art of scientific computing
- 2nd ed. University Press, Cambridge, 1992