Discussion :

[TuxThePenguin]

Bonjour,

Je travail actuellement sur un projet d'informatique qui consiste à manipuler et travaillé sur des polynômes complexe. Sur le projet en lui même je m'en sort bien. Cependant je rencontre un problème qui me bloque par une boucle infini dans ma fonction pour effectuer la division euclidienne de deux polynôme complexe (je l'ai rencontré seulement sur cette fonction pour l'instant). Le problème ne vient pas de l'implémentation de ma fonction qui est juste mais de la manière dont la machine traite les nombre a virgule, effectue des calcules et les simplifies (plus précisément lors de la multiplication ou la division de deux nombre flottant).
Je ne vais pas mettre ma fonction de division du fait de sa taille et et du nombre de fonction tierce quel appelle qui sont elle même assez imposante (addition de polynôme, soustraction de polynôme , multiplication de polynôme). J'ai donc réaliser un exemple de mon problème avec un petit code effectuant une partie du calcule de la division euclidienne de deux polynôme.
l'exemple est extrait du calcule de la division euclidienne suivante: (2+5i)z^3+(4+i)z^2+(3+2i)z+1+i divisé par (4+5i)z^2+(2+3i)z+6+2i)
après avoir fait la première soustraction et donc éliminé de z^3. La boucle se fait car le z^2 ne s'élimine jamais.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <complex.h>
int main(){
	float complex R=4+1*I;
	printf("R: %g + %gi (%f + %fi) \n",creal(R),cimag(R),creal(R),cimag(R));
	float complex A=4+5*I;
	float complex B=2+3*I;
	float complex Q=(2+5*I)/A;
	printf("Q: %g + %gi (%f + %fi) \n",creal(Q),cimag(Q),creal(Q),cimag(Q));
	float complex S=B*Q;
	printf("S: %g + %gi (%f + %fi) \n",creal(S),cimag(S),creal(S),cimag(S));
	R=R-S;
	printf("R: %g + %gi (%f + %fi) \n",creal(R),cimag(R),creal(R),cimag(R));
	Q=R/A;
	printf("Q: %g + %gi (%f + %fi) \n",creal(Q),cimag(Q),creal(Q),cimag(Q));
	S=A*Q;
	printf("S: %g + %gi (%f + %fi) \n",creal(S),cimag(S),creal(S),cimag(S));
	R=R-S;
	printf("R: %g + %gi (%f + %fi) \n",creal(R),cimag(R),creal(R),cimag(R));
	return 0;
}

J'obtiens en retour ceci:

R: 4 + 1i (4.000000 + 1.000000i)
Q: 0.804878 + 0.243902i (0.804878 + 0.243902i)
S: 0.878049 + 2.90244i (0.878049 + 2.902439i)
R: 3.12195 + -1.90244i (3.121951 + -1.902439i)
Q: 0.0725758 + -0.56633i (0.072576 + -0.566330i)
S: 3.12195 + -1.90244i (3.121951 + -1.902439i)
R: 2.38419e-07 + 0i (0.000000 + 0.000000i)

Le problème se pose sur le denier résultat stocker en mémoire (la valeur R) qui est faux car il est censé valoir 0 or comme on peut le voir, si je demande l'affichage par un %g on obtient un nombre donc la machine a stocké une valeur différente de 0 en mémoire. Lorsque j'effectue cette enchaînement de calcule avec ma calculatrice, j'obtient bien 0.

Par conséquent a cause de ce petit problème de calcule effectué par la machine ma fonction de division euclidienne dans mon projet fait une boucle infini car le reste n'est jamais un polynôme de degré inférieur au diviseur marquant ainsi la fin de la division.

Je voudrais donc savoir pourquoi je rencontrait ce problème et comment le résoudre.
Pourquoi mon dernier nombre stocké n'est pas 0?
Je trouve cela bizarre que la machine ne simplifie pas le nombre car un float est censé avoir 6 chiffre après la virgule car il est sur 32bit (comme on le vois avec l'affichage avec %f) or ici mon nombre est 0.00000023..... il devrait donc se simplifier et devenir 0 car le float stocke normalement 6 chiffre après virgule et là le 7e chiffre après la virgule est inférieur à 5.

Ne devrais je pas passé sous du double afin d'augmenter la précision?
Cependant je rencontrerai de nouveau ce problème, certes moins souvent mais il reviendra à coup sur en fonction de mes polynômes rentrés. Pareil avec du long double.

je pense que la solution est de passé en double et donc du 64 bit car ma calculatrice arrive a effectuer ces opérations sans erreurs et elle a l'aire d'être sur du 64 bit (11 chiffres après virgule), mais j'aimerais des explications sur cette simplification effectuée.


Ce que je voudrais surtout savoir c'est le pourquoi du comment en faite, pourquoi la simplification par la machine ne se fait pas

Merci d'avance de vos réponse et des explications (que qui m’intéresse le plus).

[CosmoKnacki]

le float stocke normalement 6 chiffres après virgule

C'est ici qu'est ton erreur, un float n'a justement pas un nombre de chiffre fixé après la virgule (d'où son nom de nombre à virgule flottante). Un petit tour par le wikipédia devrait t'éclaircir sur la manière dont ces nombres sont représentés. Je pense que pour t'en sortir tu dois fixer toi même une limite au-delà de laquelle tu estimes qu'un nombre est nul. L'idée est simple, comme tu effectues des calculs avec des valeurs approximatives, c'est à toi de gérer la précision. Effectivement, l'utilisation de double ne supprimera pas le problème.

[Sve@r]

Merci d'avance de vos réponse et des explications (que qui m’intéresse le plus).

Bonjour

C'est tout simple: l'ordinateur convertit les nombres décimaux en binaire exactement à l'inverse de la façon dont il convertit les entiers en binaire: en les multipliant au lieu de les diviser.

Prends par exemple le nombre 13 à convertir en binaire: on divise par 2 et on garde que les restes en s'arrêtant dès que la division arrive à 0. De là, on remonte tous les restes dans l'ordre inverse

• 13/2=6 (reste 1)
• 6/2=3 (reste 0)
• 3/2=1 (reste 1)
• 1/2=0 (reste 1)

On est arrivé à 0, on s'arrête. Le résultat est alors 1101 (2 puissance 3 + 2 puissance 2 + 2 puissance 0)

Pour les décimaux, c'est l'inverse: prends par exemple 0.625, on va le multiplier par 2 en gardant à chaque fois la partie entière et en la remettant systématiquement à 0 pour la multiplication suivante. On s'arrête quand la partie décimale arrive à 0

• 0.625 * 2 = 1.250 (on garde 1)
• 0.25 * 2 = 0.5 (on garde 0)
• 0.5 * 2 = 1.0 (on garde 1 et comme la partie décimale est à 0 on s'arrête)

Le résultat de 0.625 converti en binaire donnera alors 0.101 (2 puissance -1 + 2 puissance -3)

Malheureusement, cette façon de faire (la seule possible) fait que certains calculs ne s'arrêtent jamais. Par exemple 0.8

• 0.8 * 2 = 1.6 (on garde 1)
• 0.6 * 2 = 1.2 (on garde 1)
• 0.2 * 2 = 0.4 (on garde 0)
• 0.4 * 2 = 0.8 (on garde 0)

et etc. 0.8 converti en binaire donnera alors 0.1100110011001100 (à l'infini)
Comme l'ordi ne peut pas stocker "à l'infini", il est obligé de s'arrêter. Et si on remonte à l'envers, le nombre ne donnera peut-être pas 0.8 (0.80000000000001 ou 0.7999999999999999). C'est ce qu'on nomme "l'imprécision des flottants". Et aucune méthode au monde ne pourra corriger cela (surtout quand les calculs augmentent cette imprécision).

Pour certains calculs qui ont besoin d'être vraiment précis et exacts (comptes bancaires, etc), on utilise des librairies spécialisées qui fonctionnent généralement de la même façon: chaque chiffre est stocké sur un caractère et les calculs se font comme au primaire: chiffre par chiffre. Ainsi 2.8 + 3.7 se fera

• 7 + 8 = 15 (je retiens 1)
• 2 + 3 (+1) = 6

Résultat 6.5. Calculs bien plus longs mais toujours rigoureusement exacts. Le COBOL (langage développé spécifiquement pour les entreprises) ne fonctionne que de cette façon. C'est pour ça qu'il est massivement employé dans les banques encore aujourd'hui.

[TuxThePenguin]

Merci pour vos réponses et explications.
Je me rappelais du stockage des entier dans la mémoire, mais je ne savais pas pour les flottant. Ceci m'a pas mal éclairer (j'en ai profiter pour lire le wiki sur la norme ieee754 en lus du wiki sur le flottant ce qui ma également pas mal aidé)
J'ai donc corrigé mon problème en choisissant moi même un epsilon afin de simplifier un nombre à 0. Ceci fonctionne correctement pour des polynôme assez simple avec des monôme pas trop grand ou avec pas trop de chiffre après la virgule. Par contre pour certain polynôme je suis obligé de mettre un epsilon plus important car sinon retour dans une boucle infini lors de ma division euclidienne.

Je risque de poser une question un peut bête et évidente là mais je ne suis pas sure.
Voila pour palier à ce problème je voudrait mettre en guise d'epsilon une variable qui qui a une valeur au départ et si il est impossible de trouvé la solution sur ma division euclidienne, la changer et ainsi de suite jusque une valeur max d’epsilon. Je voudrais donc savoir si je déclare mon epsilon dans le préprocesseur, celle la sera accessible par toute mes fonction mais si je la modifie dans une fonction, gardera t'elle cette nouvelle valeur quand elle sera utilisé par la suite dans les autre fonction? Ai-je le droit d'ailleurs de modifier des variable préprocesseur ou sont elle forcément constante?

Je m'explique je déclare un epsilon de départ valant 0.000001, celui ci est utilisé dans plusieurs fonction (addition, soustraction, multiplication...) lorsque je fait la division euclidienne de deux polynôme et que celle-ci est impossible a cause de cette epsilon trop faible, je le change (par exemple en le multipliant par 10 ou en l'incrémentant par 0.000005) et je répète cette opération tant que je suis pas tombé sur un epsilon convenable. Une fois cela fait je redonne la valeur de départ de mon epsilon.

Si ceci n'est pas possible avec une variable définit dans le préprocesseur que pourrait je faire pour modifier cet epsilon qui sera souvent utiliser par plusieurs fonction.

Merci

[Sve@r]

Je voudrais donc savoir si je déclare mon epsilon dans le préprocesseur, celle la sera accessible par toute mes fonction mais si je la modifie dans une fonction, gardera t'elle cette nouvelle valeur quand elle sera utilisé par la suite dans les autre fonction? Ai-je le droit d'ailleurs de modifier des variable préprocesseur ou sont elle forcément constante?

Si ceci n'est pas possible avec une variable définit dans le préprocesseur que pourrait je faire pour modifier cet epsilon qui sera souvent utiliser par plusieurs fonction.

Le préprocesseur ne permet pas de définir de variables mais des constantes de remplacement.
Quand tu écris #define MAX 5000, et que tu compiles ton code, le compilateur génère un second code interne dans lequel tout ce qui est "MAX" devient "5000". Et c'est ce second code qui est ensuite traduit en assembleur.
Tu ne peux donc pas changer ce "MAX" en cours de route car écrire MAX=2000 serait alors compilé en 5000=2000 ce qui ne veut absolument rien dire.

C'est d'ailleurs pour ça qu'on met des parenthèses autour des macros car écrire #define SOMME(x, y) x+y poserait des soucis si ensuite ton code demandait 2*SOMME(3,4) (traduit en 2*3+4 avec un résultat de 10 au lieu de 14). Pour pallier ce soucis, on écrit alors #define SOMME(x, y) (x+y). Et on en met aussi autour des paramètres pour éviter un problème analogue dans le cas de #define CARRE(x) (x*x) qui ira dans le décors le jour où on demandera CARRE(2+3) => #define CARRE(x) ((x)*(x)).

Si tu veux avoir une variable utilisée par plusieurs fonctions, soit tu mets ta variable en globale (c'est pas super mais s'il le faut...), soit tu mets ta variable dans ton main et tu passes son adresses à tes fonctions qui auront alors loisir de la modifier si besoin. Et si tu commences à avoir plusieurs variables de ce genre, alors tu les regroupes dans une structure dédiée et c'est cette structure que tu iras trimballer de fonction en fonction (structure "s_param" par exemple)...

Par contre pour certain polynôme je suis obligé de mettre un epsilon plus important car sinon retour dans une boucle infini lors de ma division euclidienne.

Je n'ai pas vu de boucle dans ton code initial donc peut-être que ce que je vais dire n'est pas possible dans ton cas mais c'est bon à savoir: dans le cas de recherches de limites ou autre, recherches qui se font par une boucle de calculs successifs, tu n'es pas obligé d'utiliser un epsilon quelconque. Tu peux laisser ce travail à l'ordinateur.
En effet, l'ordinateur stocke ses nombres sur une largeur figée. Quelle qu'elle soit, fatalement arrivera un moment où le nombre calculé ne pourra pas être distingué du nombre précédent. A ce moment là tu peux alors arrêter ta boucle de recherche et donner son résultat.

Exemple: calcul d'une racine carrée par la limite de la suite Un+1 = ½ (Un + N/Un) (N étant le nombre dont on veut la racine et U0 pouvant être choisi de façon totalement arbitraire mais différent de 0).

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
 
// Fonction "racine"
double racine(
	float nb)				//Paramètre recevant le nombre dont on veut la racine
{
	// Déclaration des variables
	double calc;				// Calcul de la racine dans la boucle
	double diff;				// Pour tester la différence avec la valeur précédente
 
	// Si la racine n'a pas besoin d'être calculée (pour "0" ou "1")
	if (nb == 0.0 || nb == 1.0)
		return (nb);			// Ici, racine de "nb" vaut "nb"
 
	// Initialisation début de boucle
	calc=nb;				// Ou n'importe quel nombre différent de "0"
 
	do {
		// Récupération de "calc" pour comparer avec le calcul suivant
		diff=calc;
 
		// Approximation de la racine (le calcul se fera en précision "double")
		calc=0.5 * (calc + nb / calc);
 
	// Tant que le processeur peut faire la différence entre ce calcul et le précédent (limite) 
	} while (calc != diff);
 
	// Renvoi du résultat calculé
	return calc;				/* Ou bien "return diff" puisque ici, "diff" = "calc" */
}
 
// Fonction principale du programme (juste pour l'exemple) 
int main()
{
	// Déclaration des variables
	float nb;				// Nombre dont on veut la racine
 
	// Saisie et affichage de la racine
	printf("Entrez votre nombre : ");
	scanf("%f", &nb); 
	printf("La racine de %f est %lf\n", nb, racine(nb));
	return 0;
}

Dans ce calcul, je compare à chaque étape le nombre calculé avec le nombre mémorisé à l'étape précédente. Quand le processeur ne peut plus faire la différence, j'arrête ma boucle. Quoi qu'il arrive je ne peux jamais avoir de boucle infinie et je n'ai pas besoin de me casser la tête à chercher le meilleur epsilon possible car le processeur le trouve pour moi.
C'est mon prof de C qui m'avait expliqué ça à l'issue d'un contrôle où il fallait calculer une limite de suite dans un exo et où j'avais alors utilisé la technique de l'epsilon. Ce qui est amusant, c'est que comme j'étais le meilleur de la classe en C, j'avais vite écrit mon contrôle sur un brouillon et fait passer le brouillon derrière moi pour que les autres puissent aussi s'en inspirer puis réécrit mon contrôle au propre (à main levée). Et quand le prof a rendu les copies, il a dit "c'est bizarre, Frédéric a fait un truc pas mal et tout le monde a fait pareil" (il n'était pas méchant). Puis il a rajouté "mais il n'a pas fait ce qu'il y a de mieux" et c'est là qu'il nous a expliqué le truc. Peut-être que tu peux appliquer cette méthode à tes calculs...

[TuxThePenguin]

Merci de t'a réponse.
J'ai donc passer mon epsilon en paramètre de fonction (je ne voulais pas trop le faire au départ car il intervient dans les trois quart des fonction (en faite dans toute les fonction qui demande un calcule de base comme l'addition, la soustraction ou la multiplication).
C'est dommage ça que l'on peut seulement définir des constante dans le préprocesseur et pas des variable modifiable par la suite.

Pour ce qui est de mon programme, celui que j'ai mit était juste une succession de calcule pour illustrer mon problème sur les calcul de flottant. C'est pour ça qu'il n'y avait pas de boucle. Par contre pour revenir la dessus je trouve tout de même ça bizarre que cette suite de calcule censé valoir 0 me donne un nombre très petit au final (2.38419e-07 ).

Dans mon projet, j'ai implémenté une fonction pour la division euclidienne qui fait une boucle qui tant que le degré du dividende n'est pas inférieur à celui du diviseur. Une boucle infini arrivait à cause de ce genre de minuscule imprécision dans les calcule nécessaire à la division euclidienne, un degré ne pouvait plus ce supprimer car son coefficient n'était pas nul mais de 0.0000.... malgré qu'il était supérieur ou égale au degré de mon diviseur. C'est la raison pour laquelle je ne peut pas forcer cette arrêt car le résultat obtenue pour le reste et le quotient de ma division euclidienne serait pas juste.
Mais en augmentant un epsilon si la division est impossible, ma division euclidienne fonctionne à la perfection. L'epsilon étant utilisé pour simplifier à 0 des nombre inférieur à un certains seuil.

Merci de votre aide et précision technique.
Il faut maintenant que je me lance sur l'interface graphique et l’interaction avec l'utilisateur pour en finir avec mon projet (enfin pas vraiment car j'ai deux trois fonction que je n'ai pas réussi a faire du fait que je ne sais même pas le faire mathématiquement comme la factorisation, où malgré avoir lu et relu de long en large les méthodes, impossible de les comprendre, mais bon la n'est pas le sujet.)

[Sve@r]

Une boucle infini arrivait à cause de ce genre de minuscule imprécision dans les calcule nécessaire à la division euclidienne, un degré ne pouvait plus ce supprimer car son coefficient n'était pas nul mais de 0.0000.... malgré qu'il était supérieur ou égale au degré de mon diviseur.

Ca aurait fonctionné avec ma méthode: Tant que le nouveau coefficient est non nul et surtout différenciable de l'ancien...

comme la factorisation, où malgré avoir lu et relu de long en large les méthodes, impossible de les comprendre

Factorisation de polynome ? C'est comme une division (mais faut qu'elle soit possible)
Exemple: x²-7x+12 divisé par (x-3)

1. En x², combien de fois va "x": il y va "x" fois. Calcul du reste: x*x=x², oté de x² reste 0. x*(-3)=-3x, oté de -7x reste -4x. Et le "+12" reste inchangé: Il reste maintenant -4x+12 à diviser par (x-3)
2. En -4x combien de fois va "x": il y va "-4" fois. Calcul du reste: -4*x=-4x, oté de -4x reste 0. -4*(-3)=12, oté de 12 reste 0. Et c'est fini.

Résultat: x²-7x+12=(x-3)(x-4).


[edit]Remarque, même si le reste n'est pas à 0 ça doit quand-même être possible de le faire: exemple x²-7x+20=(x-3)(x-4)+8...