path: root/lib/polynom.c

/*
 *
 * Operations sur les polynomes
 *
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "polynom.h"
#include "scalaires.h"
#include "exceptions.h"
#include "main.h"
#ifdef HAVE_CONFIG_H
#include "config.h"
#else
#define _(x) x
#endif

int smartprint = 1;

/*
 * Les fonctions de base pour la construction et la destruction de polynomes 
 */
polynome ply_constr(rationnel coef, int degre)
{				/*
				 * constructeur monome 
				 */
    polynome temp;

    if (!coef.num)
	return NULL;

    temp = (monome *) Emalloc(sizeof(monome));

    temp->coef = coef;
    temp->degre = degre;
    temp->suiv = NULL;

    return temp;
}

polynome ply_vide(void)
{				/*
				 * cree un polynome 
				 */

    return NULL;
}

void ply_destruct(polynome poly)
{				/*
				 * destructeur 
				 */
    if (poly) {
	ply_destruct(poly->suiv);
	free(poly);
    }
}

polynome ply_copy(polynome poly)
{				/*
				 * recopie 
				 */
    polynome result = NULL, temp = NULL, t;

    while (poly) {
	t = ply_constr(poly->coef, poly->degre);
	if (result) {
	    temp->suiv = t;
	    temp = t;
	} else {
	    result = t;
	    temp = t;
	}
	poly = poly->suiv;
    }
    return result;
}

/*
 * Voici toutes les fonctions de manipulation de polynome. La fonction d'addition est la plus
 * importante puisqu'elle nous sert a construire un polynome entier a partir de monomes. Sa
 * structure est comparable a celle de l'operation 'fusion' dans le cas du tri fusion 
 */

polynome ply_addition(polynome poly1, polynome poly2)
{				/*
				 * addition de deux polynomes 
				 */
    polynome resultat = NULL, temp = NULL, t;
    rationnel newrat;
    int degre;

    while (poly1 && poly2) {
	if (poly1->degre > poly2->degre) {
	    t = ply_constr(poly1->coef, poly1->degre);
	    poly1 = poly1->suiv;
	} else if (poly1->degre < poly2->degre) {
	    t = ply_constr(poly2->coef, poly2->degre);
	    poly2 = poly2->suiv;
	} else {
	    newrat = rat_addition(poly1->coef, poly2->coef);
	    degre = poly1->degre;
	    t = ply_constr(newrat, degre);
	    poly1 = poly1->suiv;
	    poly2 = poly2->suiv;
	}
	if (t) {
	    if (resultat) {
		temp->suiv = t;
		temp = t;
	    } else {
		resultat = t;
		temp = t;
	    }
	}
    }

    while (poly1) {
	t = ply_constr(poly1->coef, poly1->degre);
	if (resultat) {
	    temp->suiv = t;
	    temp = t;
	} else {
	    resultat = t;
	    temp = t;
	}
	poly1 = poly1->suiv;
    }

    while (poly2) {
	t = ply_constr(poly2->coef, poly2->degre);
	if (resultat) {
	    temp->suiv = t;
	    temp = t;
	} else {
	    resultat = t;
	    temp = t;
	}
	poly2 = poly2->suiv;
    }

    return resultat;
}

/*
 * Nous avons choisi de reecrire cette fonction entierement, plutot que de bricoler a partir de la
 * fonction addition 
 */
polynome ply_soustraction(polynome poly1, polynome poly2)
{				/*
				 * soustraction de deux polynomes 
				 */

    polynome resultat = NULL, temp = NULL, t;
    rationnel newrat;
    int degre;

    while (poly1 && poly2) {
	if (poly1->degre > poly2->degre) {
	    t = ply_constr(poly1->coef, poly1->degre);
	    poly1 = poly1->suiv;
	} else if (poly1->degre < poly2->degre) {
	    t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre);
	    poly2 = poly2->suiv;
	} else {
	    newrat = rat_soustraction(poly1->coef, poly2->coef);
	    degre = poly1->degre;
	    t = ply_constr(newrat, degre);
	    poly1 = poly1->suiv;
	    poly2 = poly2->suiv;
	}
	if (t) {
	    if (resultat) {
		temp->suiv = t;
		temp = t;
	    } else {
		resultat = t;
		temp = t;
	    }
	}
    }

    while (poly1) {
	t = ply_constr(poly1->coef, poly1->degre);
	if (resultat) {
	    temp->suiv = t;
	    temp = t;
	} else {
	    resultat = t;
	    temp = t;
	}
	poly1 = poly1->suiv;
    }

    while (poly2) {
	t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre);
	if (resultat) {
	    temp->suiv = t;
	    temp = t;
	} else {
	    resultat = t;
	    temp = t;
	}
	poly2 = poly2->suiv;
    }

    return resultat;
}

/*
 * La fonction multiplication se base sur la fonction addition, suivant les mathematiques
 * classiques 
 */
polynome ply_multiplication(polynome poly1, polynome poly2)
{				/*
				 * multiplication de deux  polynomes 
				 */
    polynome temp = NULL, t, resultat = NULL, r, tempresult = NULL, poly2init;

    poly2init = poly2;
    while (poly1) {
	poly2 = poly2init;
	while (poly2) {
	    t =
		ply_constr(rat_multiplication(poly1->coef, poly2->coef),
			   poly1->degre + poly2->degre);
	    if (t) {
		if (tempresult) {
		    temp->suiv = t;
		    temp = t;
		} else {
		    tempresult = t;
		    temp = t;
		}
	    }
	    poly2 = poly2->suiv;
	}
	poly1 = poly1->suiv;
	r = ply_addition(tempresult, resultat);
	ply_destruct(resultat);
	resultat = r;
	ply_destruct(tempresult);
	tempresult = NULL;
    }

    return resultat;
}

/*
 * L'algorithme pour la division et le modulo est le meme. Seul le return change. En effet, pour
 * faire le calcul, nous utilisons la methode simple vue en cours de mathematiques, qui consiste a
 * poser la division sur une feuille et a effectuer une serie de multiplications elementaires et de 
 * soustractions. Nous obtenons donc le quotient ET le reste. 
 */

polynome ply_division(polynome dividende, polynome diviseur)
{				/*
				 * division de deux  polynomes 
				 */
    polynome interdividende = ply_copy(dividende), interdiviseur = NULL, inter = NULL, reste =
	dividende, resultat = NULL, r = NULL;
    int b = 0;

#ifdef DEBUG
    printf("On divise %s", ply_affichage(dividende));
    printf("par %s\n", ply_affichage(diviseur));
    printf("interdividende degre = %u\n", interdividende->degre);
    printf("diviseur degre = %u\n", diviseur->degre);
#endif
    while ((interdividende) && (interdividende->degre >= diviseur->degre)) {
	b = 1;
	inter =
	    ply_constr(rat_division(interdividende->coef, diviseur->coef),
		       interdividende->degre - diviseur->degre);
#ifdef DEBUG
	printf("On trouve qu'il nous faut soustraire %s fois\n", ply_affichage(inter));
#endif
	r = ply_addition(resultat, inter);
#ifdef DEBUG
	printf("Resultat intermediaire %s\n", ply_affichage(r));
#endif
	interdiviseur = ply_multiplication(diviseur, inter);
#ifdef DEBUG
	printf("On soustrait donc %s\n", ply_affichage(interdiviseur));
#endif
	reste = ply_soustraction(interdividende, interdiviseur);
#ifdef DEBUG
	printf("Reste intermediaire %s\n", ply_affichage(reste));
#endif
	ply_destruct(resultat);
	ply_destruct(inter);
	ply_destruct(interdividende);
	ply_destruct(interdiviseur);
	resultat = r;
	interdividende = reste;
    }

    if (!b)
	ply_destruct(interdividende);

    return resultat;
}

polynome ply_modulo(polynome dividende, polynome diviseur)
{				/*
				 * reste de la division de deux  polynomes 
				 */
    polynome interdividende = ply_copy(dividende), interdiviseur = NULL, inter = NULL, reste =
	dividende, resultat = NULL, r = NULL;
    int b = 0;

#ifdef DEBUG
    printf("On divise %s", ply_affichage(dividende));
    printf("par %s\n", ply_affichage(diviseur));
    printf("interdividende degre = %u\n", interdividende->degre);
    printf("diviseur degre = %u\n", diviseur->degre);
#endif
    while ((interdividende) && (interdividende->degre >= diviseur->degre)) {
	b = 1;
	inter =
	    ply_constr(rat_division(interdividende->coef, diviseur->coef),
		       interdividende->degre - diviseur->degre);
#ifdef DEBUG
	printf("On trouve qu'il nous faut soustraire %s fois\n", ply_affichage(inter));
#endif
	r = ply_addition(resultat, inter);
#ifdef DEBUG
	printf("Resultat intermediaire %s\n", ply_affichage(r));
#endif
	interdiviseur = ply_multiplication(diviseur, inter);
#ifdef DEBUG
	printf("On soustrait donc %s\n", ply_affichage(interdiviseur));
#endif
	reste = ply_soustraction(interdividende, interdiviseur);
#ifdef DEBUG
	printf("Reste intermediaire %s\n", ply_affichage(reste));
#endif
	ply_destruct(resultat);
	ply_destruct(inter);
	ply_destruct(interdividende);
	ply_destruct(interdiviseur);
	resultat = r;
	interdividende = reste;
    }

    if (!b)
	ply_destruct(interdividende);

    return b ? reste : ply_copy(reste);
}

polynome ply_exposant(polynome poly, unsigned int exp)
{				/*
				 * exponentiation d'un polynome 
				 */
    int i;
    polynome result, temp;

    if (poly) {
	result = ply_constr(rat_constr(1, 1), 0);
	for (i = 0; i < exp; i++) {
	    temp = ply_multiplication(result, poly);
	    ply_destruct(result);
	    result = temp;
	}
    } else {
	result = NULL;
    }
    return result;

}

rationnel ply_valuation(polynome poly, rationnel point)
{				/*
				 * evaluation d'un polynome en un point 
				 */
    rationnel result = rat_constr_zero();

    while (poly) {
	result = rat_addition(result, rat_multiplication(poly->coef, rat_pow(point, poly->degre)));
	poly = poly->suiv;
    }
    return result;
}

char *ply_affichage(polynome poly)
{				/*
				 * routine d'affichage d'un polynome 
				 */
    static char buf[BUFSIZ];
    char temp[BUFSIZ];
    char *rat;
    int count = 0;
    int first = 1;

    buf[0] = '\0';
    if (!poly) {
	sprintf(buf, "%s ", rat_to_string(rat_constr(0, 1), 1));
    } else {
	while (poly) {
	    if (poly->degre != 0) {
		if (smartprint) {
		    rat =
			(rat_to_double(poly->coef) ==
			 1) ? (first ? "" : "+ ") : rat_to_double(poly->coef) ==
			-1 ? (first ? "-" : "- ") : rat_to_string(poly->coef, first);
		    switch (poly->degre) {
		    case 1:
			sprintf(temp, "%s%s ", rat, mute);
			break;
		    case 2:
			sprintf(temp, "%s%s%c ", rat, mute, 178);
			break;
		    case 3:
			sprintf(temp, "%s%s%c ", rat, mute, 179);
			break;
		    default:
			sprintf(temp, "%s%s^%u ", rat, mute, poly->degre);
			break;
		    }
		} else {
		    sprintf(temp, "%s*%s^%u ", rat_to_string(poly->coef, first), mute, poly->degre);
		}
	    } else {
		sprintf(temp, "%s ", rat_to_string(poly->coef, first));
	    }
	    count += strlen(temp);
	    if (count < BUFSIZ)
		strcat(buf, temp);
	    else
		exception(2, _("ply_affichage: strcat error, not enough space in buffer"));
	    poly = poly->suiv;
	    first = 0;
	}
    }
    return buf;
}