Ergotage sur la comparaison de doubles

Bonjour,

Amené à comparer des doubles, je me pose une question quasi rhétorique sur leur comparaison : est-ce que si, dans R, a > b, un mécanisme garantit que dans du code a > b ?

Un exemple sera plus parlant qu'un long discours :
premier double a, dont la valeur réelle est 42 et dont la valeur "codée" est 42.000 000 1
second double b, dont la valeur réelle est 42.000 000 01, et dont la valeur "codée" est 42.000 000 01

Si je considère epsilon = 10^-5, on se retrouve avec dans R, a < b et dans le programme, a > b, ce qui pourrait poser des problèmes si je ne m'intéresse pas qu'au fait qu'ils soient distincts, mais bien au fait que l'un soit supérieur à l'autre.

Et si aucun mécanisme ne garantit cela (et je ne vois pas comment un tel mécanisme pourrait exister), le code de la FAQ C ne peut pas être considéré comme valide : on peut dire si la distance entre a et b est inférieur à epsilon, et dans ce cas ils sont égaux, mais on ne peut tester l'infériorité ou la supériorité que si la distance entre a et b est supérieure à epsilon.

Je ne suis pas certain d'avoir été très clair, et si c'est le cas, n'hésitez pas à me le dire pour que je reformule.

J'ai vu ta question. Elle m'intéresse, mais j'ai besoin de temps pour réfléchir au problème.

Citation:

---

Envoyé par gangsoleil

On ne peut tester l'infériorité ou la supériorité que si la distance entre a et b est supérieure à epsilon

---

Vous avez raison. Si vous avez envie d'approfondir le sujet, cet article est assez intéressant.

Bonjour

Partons du point de vue de la machine: pour elle, 42.0 (dans ton exemple) n'existe pas. Elle, elle ne voit que 42.000 000 100. Or, 42.000 000 100 étant bel et bien supérieur à 42.000 000 010, aucun mécanisme ne pourra arranger cela. Et si un tel mécanisme était tenté, le premier soucis de son programmeur serait de faire la différence entre un vrai 42.000 000 100 et 42.0 qui serait codé en 42.000 000 100.:mur:

Tu retombes sur le problème de l'exactitude des calculs en double quand ça s'avère expressément nécessaire (comptes bancaires par exemple) qui nécessitent l'emploi de librairies dédiées (comme Decimal en Python et je suppose qu'il doit en exister en C mais je ne les connais pas) ou de langages dédiés (comme le COBOL) et qui fonctionnent à base de chiffres positionnés un à un dans des cases distinctes. A ce moment là, 42.0 occupe 3 digits (PIC 99V9 en COBOL).

Je ne comprend pas l'exemple que tu cites : Si |a|<|b|, je ne vois pas comment la valeur codée pour |a| pourrait être supérieure à la valeur codée pour |b|

Citation:

---

Envoyé par diogene

Je ne comprend pas l'exemple que tu cites : Si |a|<|b|, je ne vois pas comment la valeur codée pour |a| pourrait être supérieure à la valeur codée pour |b|

---

C'est vrai, elle ne peut certainement pas être supérieure (les puissances de deux, même en négatif, restent dans l'ordre relatif de leurs valeurs respectives)

Toutefois rien ne garantit qu'elle sera toujours vue comme étant inférieure...

Code:

---

1 2 3 4 5 6 7 8

#include <stdio.h>   int main() { double a=2.97999999999999999; double b=2.98; printf("%s\n", a < b ?"vrai" :"faux"); }

---

Citation:

---

Toutefois rien ne garantit qu'elle sera toujours vue comme étant inférieure...

---

Evidemment, elles peuvent être vues comme égales. Mais ça, c'est la question classique de la comparaison à l'égalité de deux flottants. Cela ne correspond pas à l'exemple cité dans le premier post.

Citation:

---

Envoyé par Sve@r

C'est vrai, elle ne peut certainement pas être supérieure (les puissances de deux, même en négatif, restent dans l'ordre relatif de leurs valeurs respectives)

Toutefois rien ne garantit qu'elle sera toujours vue comme étant inférieure...

---

Cela dit, les valeurs ne sont pas supérieures non plus (avec visual C++ 2008 pour un XP 32bits)
Pour moi, le code suivant affiche faux pour les deux tests.

Code:

---

1 2 3 4 5 6 7 8

#include <stdio.h> int main() { double a=2.97999999999999999; double b=2.98; printf("2.97999...<2.98 ? %s\n", a < b ?"vrai" :"faux"); printf("2.97999...>2.98 ? %s\n", a < b ?"vrai" :"faux"); }

---

Citation:

---

Envoyé par diogene

Je ne comprend pas l'exemple que tu cites : Si |a|<|b|, je ne vois pas comment la valeur codée pour |a| pourrait être supérieure à la valeur codée pour |b|

---

Dans R, j'aurai a qui vaut 42, et b qui vaut 42, pas de soucis.

Dans un monde discret, a et b sont représentés à epsilon près, par exemple, si epsilon vaut 3*10^-6
a pourrait être codé, par exemple, 42.000 001
b pourrait être codé, par exemple, 41.999 999

Et comme on le sait, pour savoir si a == b, on fait la différence entre a et b et on compare cette différence à epsilon.


Bien. Maintenant, dans R, j'ai a qui vaut 42.000 001, et b qui vaut 42.000 0002
Dans mon ordi, chaque nombre est codé à epsilon près, ce qui pourrait donner :
a = 42.000 002
b = 42.000 001

Dans ce cas précis, dans R, a < b, mais dans l'ordi a > b. En fait, ce que je dis, c'est que dans le cas où (a-b) < epsilon, on ne peut pas dire que a > b ou a < b. Et donc ce que je dis aussi, c'est que le code qui est dans la FAQ n'est pas bon.

Pour moi, le code devrait ressembler à cela -- sauf qu'ici je ne gère qu'un seul epsilon, et que la fonction abs() prend un int en entrée :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int compare_double (double a, double b, double epsilon) { int ret;   if (abs(b-a) < epsilon) { ret = 0; /* ils sont égaux */ } else { if ( a < b ) { ret = -1; } else { ret = 1; } }   return ret;

---

Citation:

---

Bien. Maintenant, dans R, j'ai a qui vaut 42.000 001, et b qui vaut 42.000 0002
Dans mon ordi, chaque nombre est codé à epsilon près, ce qui pourrait donner :
a = 42.000 002
b = 42.000 001

---

C'est ça que je ne crois pas possible : le nombre |a| est codé par une certaine approximation de sa valeur réelle. Celle-ci peut être, (1) la plus grande valeur codable inférieure ou égale à |a|, (2) la plus petite valeur codable supérieure ou égale à |a|, (3) la valeur codable la plus proche de |a|.
Ce peut être une option du compilateur que de choisir parmi ces possibilités, mais elle s'applique à l'ensemble des flottants. Dans ces trois choix, la configuration que tu évoques ne peut se produire.

Faut-il envisager le cas d'utilisation d'unités de compilation séparées qui auraient été compilées avec des options différentes ?

Citation:

---

En fait, ce que je dis, c'est que dans le cas où (a-b) < epsilon, on ne peut pas dire que a > b ou a < b.

---

Cela revient à définir un nouvel ensemble d'opérateurs de comparaison. Au lieu de a==b, le nouvel et virtuel opérateur 'égal' correspond à (a-b) < epsilon
On doit normalement également préciser de nouveaux opérateurs 'plus grand' et 'plus petit'.
Dans ce nouvel ensemble de comparaison, un nombre ne doit pas pouvoir être à la fois 'égal' et 'plus grand', ou 'égal' et 'plus petit', ou 'plus grand' et 'plus petit' ...pour une question de cohérence de cet ensemble d'opérateurs.
On peut définir le nouvel ensemble d'opérateurs en fonction de l'ancien mais il faut ensuite choisir quel ensemble d'opérateurs on utilise et mélanger les deux n'a pas grand sens : " Si a 'egal' b, on ne peut pas dire que a > b ou a < b "

Citation:

---

Envoyé par diogene

le nombre |a| est codé par une certaine approximation de sa valeur réelle. Celle-ci peut être, (1) la plus grande valeur codable inférieure ou égale à |a|, (2) la plus petite valeur codable supérieure ou égale à |a|, (3) la valeur codable la plus proche de |a|.
Ce peut être une option du compilateur que de choisir parmi ces possibilités, mais elle s'applique à l'ensemble des flottants. Dans ces trois choix, la configuration que tu évoques ne peut se produire.

---

La configuration a < b dans R et a > b dans la représentation discrète non, effectivement. Mais (encore une fois, cette discussion est purement théorique, et n'a pour but que de chercher la petite bête) d'après ce que tu dis, on pourrait avoir la configuration suivante (avec epsilon qui convient bien sur, un truc du genre 3*10^-8 ):
Cas 1 : la plus grande valeur codable inférieure ou égale à |nombre|
a = 42.000 000 001 dans R, représentable par a = 42.000 000 010 (ceci est purement théorique)
b = 42.000 000 010 dans R, représentable par b = 42.000 000 010

Dans R, a < b, alors que dans l'espace discret a = b. Donc certes, l'inversion n'est pas possible, mais on peut théoriquement se retrouver à tester si a < b et que la réponse soit fausse, car a et b sont codés de la même manière.

Enfin seulement si je n'ai pas tout compris de travers, ce qui est toujours possible.

Citation:

---

mais on peut théoriquement se retrouver à tester si a < b et que la réponse soit fausse, car a et b sont codés de la même manière.

---

Oui. Mais la question n'a pas plus de sens que la question de l'égalité des deux flottants testé avec l'opérateur == : A partir du moment où on considère que l'égalité est indéterminée, les questions "plus grand" ou "plus petit" ont une réponse indéterminée.

En redéfinissant l'égalité à partir de epsilon, on cherche à faire que la réponse soit bien définie et il faut redéfinir "plus grand" ou "plus petit" à partir de cette nouvelle définition de l'égalité.

Citation:

---

Envoyé par gangsoleil

Dans R, j'aurai a qui vaut 42, et b qui vaut 42, pas de soucis.

Dans un monde discret, a et b sont représentés à epsilon près, par exemple, si epsilon vaut 3*10^-6
a pourrait être codé, par exemple, 42.000 001
b pourrait être codé, par exemple, 41.999 999

Citation:

---

Envoyé par diogene

C'est ça que je ne crois pas possible : le nombre |a| est codé par une certaine approximation de sa valeur réelle. Celle-ci peut être, (1) la plus grande valeur codable inférieure ou égale à |a|, (2) la plus petite valeur codable supérieure ou égale à |a|, (3) la valeur codable la plus proche de |a|.
Ce peut être une option du compilateur que de choisir parmi ces possibilités, mais elle s'applique à l'ensemble des flottants. Dans ces trois choix, la configuration que tu évoques ne peut se produire.

---

---

C'est vrai que plus je réfléchis à la façon dont sont convertis les nombres décimaux, plus je pense aussi que ce n'est pas possible. Et je ne pense même pas qu'il y ait 3 façons différentes de les coder.
Parce que moi, j'ai appris que les décimaux étaient codés de la façon suivante (inverse de la façon dont on code les entiers): en les multipliant et en ne conservant que la partie entière du résultat tout en la remettant à 0
Exemple: 0.625

• 0.625 * 2 = 1.250 => on garde 1 et on repart de 0.250
• 0.250 * 2 = 0.5 => on garde 0
• 0.5 * 2 = 1 => on garde 1 et comme le reste est à 0 c'est fini

Résultat: 0.625 = 0.101 en binaire

Et c'est cette façon de faire (à mon avis la seule possible) qui induit l'imprécision. Par exemple 0.3

• 0.3 * 2 = 0.6
• 0.6 * 2 = 1.2
• 0.2 * 2 = 0.4
• 0.4 * 2 = 0.8
• 0.8 * 2 = 1.6
• 0.6 * 2 = 1.2
• ...

Donc 0.3 ne sera jamais codé exactement 0.3 en binaire. Si on s'arrête à 7 digits, cela donnera alors 0.0100110 (binaire) qui, retransformé en décimal, donne alors 0.296875. Mais cette méthode ne permet pas d'avoir et a<b dans R et a (binaire) > b (binaire). Après-tout, cette façon de coder décompose le nombre décimal en puissances négatives de 2 (0.625 = 2^(-3) + 2^(-1)) tout comme la méthode des divisions successives décompose le nombre entier en puissances positives de 2 (10=2^3+2^1=1010). Mais même écrites sous formes d'une liste de puissances négatives de 2, et même quand cette liste est tronquée à n digits, les grandeurs relatives de deux nombres restent respectées l'une par rapport à l'autre.
Depuis hier j'essaye vainement d'imaginer des combinaisons qui feraient que... Par exemple 0.3 (ou en absolu 0.296875) donne 0.0100110 et 0.0100111 (à peine plus grand) donne 0.3046875 lui-aussi plus grand que 0.296875. Et 0.0100101 (à peine plus petit) donne 0.2890625 lui-aussi plus petit que 0.296875. Et donc à mon avis je n'en trouverai pas parce que les mathématiques sont contre moi. Après-tout, quand je passe de 0.0100110 à 0.0100111, c'est bien une fraction de 2 que j'ajoute au nombre initial. Et cet ajout ne me parait pas pouvoir donner alors un nombre plus petit que le nombre initial...

Citation:

---

Envoyé par Sve@r

Par exemple 0.3 (ou en absolu 0.296875) donne 0.0100110 et 0.0100111 (à peine plus grand) donne 0.3046875

---

Je ne suis peut-être pas bien réveillé, mais considère 0.010 011 000 001 : il est bien inférieur à la valeur réelle, et supérieur à la valeur "codée" de 3, non ?

Sauf qu'il n'existe pas du tout pour le C++.
Ce nombre n'est pas représentable, et sera approximé par la même chose que 0.3, sinon, 0.3 aurait une représentation plus précise.

L'espace de valeurs des doubles est limité, non dense, et surtout, pas régulièrement peuplé selon les plages de valeurs.

Citation:

---

Envoyé par gangsoleil

Je ne suis peut-être pas bien réveillé, mais considère 0.010 011 000 001 : il est bien inférieur à la valeur réelle, et supérieur à la valeur "codée" de 3, non ?

---

L'exemple que j'ai pris était vu dans un univers informatique théorique limité à 8 décimales. Dans un tel monde, comme le dit leternel, 0.010 011 000 001 n'existe pas et est vu alors comme 0.010 011 00 qui redevient la représentation de 0.3 (d'où mon premier code où je montre que deux nombres différents sont vus de façon identique).

On peut bien entendu créer un exemple analogue à 12 décimales. Dans ce cas, 0.3 sera codé 0.010 011 001 100 et redonnera en retour 1/4 + 1/32 + 1/64 + 1/512 + 1/1024 soit 0,299804688.
Et dans ce cas, 0.010 011 001 101 qui, dans un monde à 12 décimales, se trouve être alors le premier nombre immédiatement supérieur, donnera alors 1/4 + 1/32 + 1/64 + 1/512 + 1/1024 + 1/4096 soit 0,300048828 toujours supérieur à 0,3.

Ce même mécanisme s'appliquera ainsi de façon équivalente dans le vrai monde informatique qui, quelle que soit sa précision, reste quand-même limitée, finie et identique pour tous les nombre décimaux traités...

PS: a noter que cette méthode de muliplications successives n'est pas la plus fine car 0.3 (codé sur 12 décimales) donne 0.299804688 soit un écart de 19E-5 avec le nombre initial. Alors que si on rajoute 1/4096 cela donne 0.300048828 qui n'a plus qu'un écart de 4.8E-5 avec le nombre initial. Mais (à ma connaissance) il n'y en a pas d'autre.