/**************************************************** * Euclidian division of two polynomials * * R(x) = P(x) / Q(x) * * ------------------------------------------------- * * Ref.: "Mathématiques en Turbo-Pascal By M. Ducamp * * and A. Reverchon (vol 2), Eyrolles, Paris, 1988" * * [BIBLI 05]. * * ------------------------------------------------- * * SAMPLE RUN: * * * * EUCLIDIAN DIVISION OF TWO POLYNOMIALS: * * * * P(x) = 2x5 +2x3 -x2 +2x -1 * * Q(x) = x3 -1 * * * * * * Quotient: * * * * +2 X2 +2 * * * * Remainder: * * * * + X2 +2 X +1 * * * * ------------------------------------------------- * * 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) * ****************************************************/ #include #include #include #include "polynoms.h" ar_polynom *P, *Q, *H, *R; bool DivPolynom(ar_polynom *P, ar_polynom *Q, ar_polynom *H, ar_polynom *R) { int i,j; ar_number u; ar_polynom *nh, *nr; nh = (ar_polynom *) calloc(1,sizeof(ar_polynom)); nr = (ar_polynom *) calloc(1,sizeof(ar_polynom)); //The Q polynomial must be <> zero if (Q->degree==0 && Q->coeff[0].value==0) return FALSE;; nr->degree=P->degree; for (i=0; i<=P->degree; i++) nr->coeff[i]=P->coeff[i]; nh->degree = P->degree - Q->degree; if (nh->degree<0) { nh->degree=0; if (!SetNumber(&nh->coeff[0],"0")) return FALSE; } else { for (i=nh->degree; i>=0; i--) { if (!DivNumber(nr->coeff[nr->degree],Q->coeff[Q->degree], &nh->coeff[i])) return FALSE; for (j=i; j<=nr->degree; j++) { if (!MultNumber(nh->coeff[i],Q->coeff[j-i], &u)) return FALSE; u.p=-u.p; u.value=-u.value; if (!AddNumber(nr->coeff[j],u, &nr->coeff[j])) return FALSE; } if (nr->degree > 0) nr->degree--; } while (fabs(nr->coeff[nr->degree].value) < AR_SMALL && nr->degree>0) nr->degree--; } H->degree=nh->degree; for (i=0; i<=nh->degree; i++) H->coeff[i]=nh->coeff[i]; R->degree=nr->degree; for (i=0; i<=nr->degree; i++) R->coeff[i]=nr->coeff[i]; free(nh); free(nr); return TRUE; } //DivPolynom() void main() { //dynamic memory allocation of 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 EUCLIDIAN DIVISION OF TWO POLYNOMIALS:\n\n"); if (!EnterPolynom(" P(X) = ", P)) return; if (!EnterPolynom(" Q(X) = ", Q)) return; printf("\n\n"); if (DivPolynom(P,Q,H,R)) { printf(" Quotient:\n"); DisplayPolynom(H); printf("\n"); printf(" Remainder:\n"); DisplayPolynom(R); } else printf(" Error in Euclidian division."); printf("\n\n"); free(P); free(Q); free(H); free(R); } // end of file divpol.cpp