/**************************************************** * Division of two polynomials by increasing powers * * k * * P(x) = Q(x).H(x) + x.R(x) * * ------------------------------------------------- * * Ref.: "Mathématiques en Turbo-Pascal By M. Ducamp * * and A. Reverchon (vol 2), Eyrolles, Paris, 1988" * * [BIBLI 05]. * * ------------------------------------------------- * * SAMPLE RUN: * * * * DIVISION OF TWO POLYNOMIALS BY INCREASING POWERS: * * * * P(x) = 2x2 +x * * Q(x) = x3 -x2 +1 * * Order: 4 * * * * * * Quotient: * * * * + X3 +2 X2 + X * * * * Remainder: * * * * - X2 - X +1 * * * * * * DIVISION OF TWO POLYNOMIALS BY INCREASING POWERS: * * * * P(x) = 3/5x3 +2x -4 * * Q(x) = x2 -5/4 * * Order: 9 * * * * * * Quotient: * * * * +4096/3125 X8 -704/625 X7 +1024/625 X6 -176/125 X5* * +256/125 X4 -44/25 X3 +64/25 X2 -8/5 X +16/5 * * * * Remainder: * * * * -4096/3125 X +704/625 * * * * ------------------------------------------------- * * Functions used (of module Polynoms): * * * * AddNumber(), EnterPolynom(), DivNumber(), * * DisplayPolynom(), MultNumber() and SetNumber(). * * * * C++ version by J-P Moreau. * * (To be linked with polynoms.cpp).* * (www.jpmoreau.fr) * ***************************************************** Explanations: Given two polynomials P(x) and Q(x) and an integer k, it exists a couple of polynomials H(x) and R(x), such as: Px) = Q(x).H(x) + x^k.R(x) The degree of H(x) is < k. Note: the constant coefficient of Q(x) must be <> 0. ----------------------------------------------------*/ #include //for printf() #include //for calloc() #include "polynoms.h" //for EnterPolynom() etc. ar_polynom *P,*Q,*H,*R; int k; //Division of two polynomials by increasing powers bool DivPolynom1(ar_polynom *P,ar_polynom *Q, int k,ar_polynom *H,ar_polynom *R) { int i,j,mx; ar_number u; //The Q polynomial constant term and k must be <> zero if (k<=0 || Q->coeff[0].value==0) return FALSE;; mx=Q->degree+k-1; if (mxdegree) mx=P->degree; if (mx>Q->degree) for (i=Q->degree+1; i<=mx; i++) if (!SetNumber(&Q->coeff[i],"0")) return FALSE; for (i=0; i<=P->degree; i++) R->coeff[i]=P->coeff[i]; if (k>Q->degree) for (i=Q->degree+1; i<=k; i++) if (!SetNumber(&Q->coeff[i],"0")) return FALSE; for (i=0; icoeff[i],Q->coeff[0],&H->coeff[i])) return FALSE; for (j=1; j<=mx; j++) { if (!MultNumber(H->coeff[i],Q->coeff[j-i], &u)) return FALSE; u.p=-u.p; u.value=-u.value; if (!AddNumber(R->coeff[j], u, &R->coeff[j])) return FALSE; } } H->degree=k-1; while (H->degree>0 && H->coeff[H->degree].value==0) H->degree--; R->degree=mx-k; for (i=0; i<=R->degree; i++) R->coeff[i]=R->coeff[i+k]; while (R->degree>0 && R->coeff[R->degree].value==0) R->degree--; return TRUE; } //DivPolynom1() void main() { //dynamic memory allocation for polynomials P = (ar_polynom *) calloc(1,sizeof(ar_polynom)); Q = (ar_polynom *) calloc(1,sizeof(ar_polynom)); H = (ar_polynom *) calloc(1,sizeof(ar_polynom)); R = (ar_polynom *) calloc(1,sizeof(ar_polynom)); printf("\n DIVISION OF TWO POLYNOMIALS BY INCREASING POWERS:\n\n"); if (!EnterPolynom(" P(X) = ", P)) return; if (!EnterPolynom(" Q(X) = ", Q)) return; printf("\n Order: "); scanf("%d",&k); printf("\n\n"); if (DivPolynom1(P,Q,k,H,R)) { printf(" Quotient:\n"); DisplayPolynom(H); printf("\n Remainder:\n"); DisplayPolynom(R); } else printf(" Error in Division by increasing powers."); printf("\n\n"); free(P); free(Q); free(H); free(R); } // end of file divpol1.cpp