[C] Multiplication de polynômes. Ce code est-il OK ? [Résolu]

Multiplication de polynômes. Ce code est-il OK ? [Résolu] [C] - C - Programmation

Marsh Posté le 28-04-2005 à 12:32:05    

Salut,
 
Voilà ,j'ai fait un code assez simple permettant la multiplication de polynômes. Je manipule des tableaux. L'indice du tableau traduit le degré et la valeur pour un indice traduit le coefficient.
 

Code :
  1. int MulPoly (const int Pol1[], const int Pol2[], int Resultat[])
  2. {
  3. int i, j;
  4. for (i=0; i<DEGRE_POLY + 1; i++)
  5.    {
  6.  /* On additionne dans 'Resultat' le produit des coeff de  
  7.     même degré d'où le '+=' */
  8.  for (j = 0; j<DEGRE_POLY + 1; j++)
  9.   Resultat[i + j] += Pol1[i] * Pol2[j];
  10.    }
  11. return 0;
  12. }


 
J'ai testé avec des polynômes de faible degré et c'était OK. Mais j'ai des résultats inattendus avec des polynômes de degré 24. Je ne sais si c'est mon code qui est faux ou si c'est ailleurs dans le programme que ça déconne.
 
Merci !
 :hello:


Message édité par yoms le 28-04-2005 à 22:31:45
Reply

Marsh Posté le 28-04-2005 à 12:32:05   

Reply

Marsh Posté le 28-04-2005 à 12:42:23    

0 <= i + j <= 2 * DEGRE_POLY

Reply

Marsh Posté le 28-04-2005 à 15:27:29    

J'ai corrigé le code ci-dessus. Je m'étais trompé dans le nom des cstes de degré. Je n'ai pas bien compris ce que tu voulais dire, mais peut-être que ma correction prend en compte ta remarque.
 
Pol1 est de taille DEGRE_POLY + 1 (le +1 pour la puissance zéro)
Pol2 est de taille DEGRE_POLY + 1
Resultat est de taille 2 * DEGRE_POLY + 1

Reply

Marsh Posté le 28-04-2005 à 15:30:46    

Non, Resultat est de taille 2 * (DEGRE_POLY + 1)

Reply

Marsh Posté le 28-04-2005 à 15:43:44    

Si DEGRE_POLY == 24, le degré du résultat est la somme des degrés de chaque poly, soit 48. Pour le tableau, sachant que je commence au degré 0, il me faut donc 49 "cases" pur stocker mon résultat, soit 2 * 24 + 1 <=> 2 * DEGRE_POLY + 1.
 
J'aurais une eu belle erreur d'écriture en-dehors des limites sinon.
 
Mais l'algo en soit, il est faux ou pas ?

Reply

Marsh Posté le 28-04-2005 à 16:01:16    

Ou à la rigueur, il n'y a pas un soft qui fait ça que je peux DL afin de comparer mes résultats ?

Reply

Marsh Posté le 28-04-2005 à 18:52:06    

Ca m'a l'air correct en supposant que le résultat est bien initialisé à 0 avant l'algorithme.
 
Sinon c'est l'algorithme naïf pour la multiplication si tu veux quelque chose d'un peu plus efficace regarde Karatsuba.


Message édité par Tarabiscote le 28-04-2005 à 18:52:42
Reply

Marsh Posté le 28-04-2005 à 22:31:17    

Tarabiscote a écrit :

Ca m'a l'air correct en supposant que le résultat est bien initialisé à 0 avant l'algorithme.
 
Sinon c'est l'algorithme naïf pour la multiplication si tu veux quelque chose d'un peu plus efficace regarde Karatsuba.


 
Tout à fait, le tableau de résultat est bien initialisé à zéro. J'ai pondu ça en 5 min, mais comme on a un truc qui déconne et que je n'ai pas envie de me taper la multiplication de deux poly de degré 23 et 24 pour vérifier, j'ai sollicité vos avis.
Merci à tous.
 
PS : je vais jeter un oeil à Karatsuba

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed