/****************************************************
*     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 <stdio.h>
#include <malloc.h>
#include <math.h>

#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