title: Polynomial Greatest Common Divisor C++
body: <p>Here is my attempt to implement a program that finds GCD of two polynomials.
  I realize there is a problem in division method. A while loop decrementing the degree of a resulting polynomial in <code>division()</code> goes into "infinity" in some cases, and I can't understand in which exactly.</p>
  
  <p><em>Any clues on what goes wrong here?</em></p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;stdlib.h&gt;
  
  
  
  using namespace std;
  
  //polynomial------------------------------
  struct polynomial {
      float *coeff;
      int degree;
  };
  
  /*function declaration */
  int get_data(polynomial *P); 
  int display(polynomial *P);
  int division(polynomial *P, polynomial *Q, polynomial *H, polynomial *R);
  int polcpy(polynomial *p, polynomial *q);
  void GCDPol(polynomial *P,polynomial *Q, polynomial *R);
  
  //GCD of two polynomials------------------
  void GCDpol(polynomial *P,polynomial *Q, polynomial *R) {
      polynomial *res, *v;
      res = (polynomial *) calloc(1,sizeof(polynomial));  
      v = (polynomial *) calloc(1,sizeof(polynomial));  
      while(1) {
          division(P, Q, v, R);
          if(R-&gt;degree==0 &amp;&amp; R-&gt;coeff[0]==0)
              break;
          else
              polcpy(P,Q);
              polcpy(Q,R);
      }
      polcpy(R,Q);
      free(res);
      free(v);
  }
  
  //pol copy--------------------------------
  int polcpy(polynomial *p, polynomial *q) {
      p-&gt;degree=q-&gt;degree;
      p-&gt;coeff = new float[p-&gt;degree + 1];
      for (int i=0; i&lt;=p-&gt;degree; i++) 
          p-&gt;coeff[i]=q-&gt;coeff[i];
      return 0;
  }
  
  //division--------------------------------
  int division(polynomial *P, polynomial *Q, polynomial *H, polynomial *R) {
      float u;
      int x;
      polynomial *nh, *nr;
      nh = (polynomial *) calloc(1,sizeof(polynomial));
      nr = (polynomial *) calloc(1,sizeof(polynomial));
  
      /*Euclidian Long Division*/
      polcpy(nr, P);  
      nh-&gt;degree = P-&gt;degree - Q-&gt;degree;
      nh-&gt;coeff = new float[nh-&gt;degree + 1];
      for (int i=nh-&gt;degree; i&gt;=0; i--)  {
          nh-&gt;coeff[i] = nr-&gt;coeff[nr-&gt;degree] / Q-&gt;coeff[Q-&gt;degree];
          for (int j=i; j &lt;= nr-&gt;degree; j++) {
              u = nh-&gt;coeff[i] * Q-&gt;coeff[j-i];
              nr-&gt;coeff[j] = nr-&gt;coeff[j] - u;
          }
          if (nr-&gt;degree &gt; 0)  
              nr-&gt;degree--;
      }
  
      /*Quotient*/
      polcpy(H, nh);  
      /*Remainder*/   
      polcpy(R, nr);
      while(R-&gt;coeff[R-&gt;degree] == 0) {
          R-&gt;degree--;
      }   
      free(nh); 
      free(nr);
      return 0;
  }
  
  //display-------------------------------
  int display(polynomial *P) {
      int i, j;
      for (i = P-&gt;degree; i &gt;= 0; i--) {
          cout &lt;&lt; P-&gt;coeff[i] &lt;&lt; "x^" &lt;&lt; i;
          if ((i - 1) != -1)
              cout &lt;&lt; "+";
      }
      cout &lt;&lt; "\n";
      return 0;
  }
  
  //get_data------------------------------
  int get_data(polynomial *P) {
      cout &lt;&lt; "Enter Degree Of Polynomial:";
      cin &gt;&gt; P-&gt;degree;
      P-&gt;coeff = new float[P-&gt;degree + 1];
      for (int i = P-&gt;degree; i &gt;= 0; i--) {
          cout &lt;&lt; "Enter coefficient of x^" &lt;&lt; i &lt;&lt; ":";
          cin &gt;&gt; P-&gt;coeff[i];
      }
      return 0;
  }
  
  
  int main() {
      polynomial *P, *Q, *R, *H;
      P = (polynomial *) calloc(1,sizeof(polynomial));
      Q = (polynomial *) calloc(1,sizeof(polynomial));
      R = (polynomial *) calloc(1,sizeof(polynomial));
      H = (polynomial *) calloc(1,sizeof(polynomial));
      cout&lt;&lt;"GDC\n";
      get_data(P);
      get_data(Q);
      cout &lt;&lt; "Polynomial1:";
      display(P);
      cout &lt;&lt; "Polynomial2:";
      display(Q);
      GCDpol(P,Q,R);
      display(R);
      free(R);
      free(P);
      free(Q);
      free(H);
      return 0;
  }
  </code></pre>