Plus grand diviseur commun polynomial C++

Question

Voici ma tentative d'implémenter un programme qui trouve GCD de deux polynômes. Je réalise qu'il y a un problème dans la méthode de division. Une boucle while décrémentant le degré d'un polynôme résultant dans division() va dans "l'infini" dans certains cas, et je ne peux pas comprendre exactement dans lequel.

Des indices sur ce qui ne va pas ici?

#include<iostream> 
#include<stdlib.h> 



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->degree==0 && R->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->degree=q->degree; 
    p->coeff = new float[p->degree + 1]; 
    for (int i=0; i<=p->degree; i++) 
     p->coeff[i]=q->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->degree = P->degree - Q->degree; 
    nh->coeff = new float[nh->degree + 1]; 
    for (int i=nh->degree; i>=0; i--) { 
     nh->coeff[i] = nr->coeff[nr->degree]/Q->coeff[Q->degree]; 
     for (int j=i; j <= nr->degree; j++) { 
      u = nh->coeff[i] * Q->coeff[j-i]; 
      nr->coeff[j] = nr->coeff[j] - u; 
     } 
     if (nr->degree > 0) 
      nr->degree--; 
    } 

    /*Quotient*/ 
    polcpy(H, nh); 
    /*Remainder*/ 
    polcpy(R, nr); 
    while(R->coeff[R->degree] == 0) { 
     R->degree--; 
    } 
    free(nh); 
    free(nr); 
    return 0; 
} 

//display------------------------------- 
int display(polynomial *P) { 
    int i, j; 
    for (i = P->degree; i >= 0; i--) { 
     cout << P->coeff[i] << "x^" << i; 
     if ((i - 1) != -1) 
      cout << "+"; 
    } 
    cout << "\n"; 
    return 0; 
} 

//get_data------------------------------ 
int get_data(polynomial *P) { 
    cout << "Enter Degree Of Polynomial:"; 
    cin >> P->degree; 
    P->coeff = new float[P->degree + 1]; 
    for (int i = P->degree; i >= 0; i--) { 
     cout << "Enter coefficient of x^" << i << ":"; 
     cin >> P->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<<"GDC\n"; 
    get_data(P); 
    get_data(Q); 
    cout << "Polynomial1:"; 
    display(P); 
    cout << "Polynomial2:"; 
    display(Q); 
    GCDpol(P,Q,R); 
    display(R); 
    free(R); 
    free(P); 
    free(Q); 
    free(H); 
    return 0; 
} 

Answer 1

Il semble probable que la ligne

if(R->degree==0 && R->coeff[0]==0) 
     break; 

est ce qui est cassé. Vos coefficients sont des flottants. Parce que les ordinateurs sont (malheureusement) finis, il y aura de petites erreurs dans votre calcul de float. Le code ne sort que de la boucle while si le coefficient est exactement 0. Il semble probable que sur certaines entrées, bien qu'il faille diviser uniformément, vous obtenez R->coeff[0] = 0.0000000001 ou une autre valeur très petite qui n'est pas exactement 0.

Essayez de vérifier si la valeur absolue est dans une très petite tolérance (quelque chose comme 10^-10 ou 10^-12.) Si vous voulez réellement la valeur exacte, vous devez regarder dans les flotteurs de précision exacte, qui est sa propre boîte de Pandore.

(En regardant le code de plus près, vous faites des contrôles d'égalité exactes dans d'autres endroits aussi - ceux-ci devraient tous être modifiés pour vérifier la valeur absolue est très faible.)

Answer 2

while(R->coeff[R->degree] == 0) { 
    R->degree--; 
} 

Cela va très mal si R est le polynôme zéro.