/****************************************************
* 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 <stdio.h>      //for printf() 
#include <malloc.h>     //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 (mx<P->degree)  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; i<k; i++)  {
      if (!DivNumber(R->coeff[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