Discussion :

[Médinoc]

Franchement, mes virgules fixes, je les vois de l'autre façon:

• Virgule fixe décimale, deux chiffres après la virgule: On stocke la valeur bêtement multipliée par 100, 1.3 est stocké en tant que 130.
• Virgule fixe binaire, 8 bits après la virgule: On stocke la valeur décalée. Impossible de stocker certaines valeurs décimales, mais une valeur comme 42.25 serait encodée ainsi: 00101010.01000000

[Jean-Marc.Bourguet]

La précision en virgule fixe est paramétrable, contrairement à celle des flottants...

Il y a des bibliotheques de flottants avec une precision variable, tout comme il y a des bibliotheques de flottant basee sur une base decimale et des bibliotheques en virgule fixe avec un certain nombre de variantes.

Mon probleme est que tu presentes comme valables pour toutes les variantes des virgules fixes des caracteristiques qui ne sont presentes que pour certaines d'entre elles, et qui sont presentes aussi avec certains formats de virgule flottante.

Ses chiffres sont d'ores et déjà décimaux, donc finis, et il n'utilise que les opérations d'addition/soustraction (donc pas de division produisant un irrationnel).

La representation est garantie finie si la base utilisee a 5 et 2 comme facteur premier, sinon certains nombres ont une representation dans celle-ci qui est infinie.

Prenons un exemple plus parlant : "524.4322". Cela donnerait (précision 10^9 / 10^-9) "0x0000020C.10E20000" (j'ai introduit le "." pour montrer la position de la virgule fixe).

OK, ca c'est une representation base 10^9 avec les chiffres codes sur 32 bits.
En BCD, une autre representation en virgule fixe en base 10 avec les chiffres codes sur 4 bits, aurait donne 0x00000524.43220000. Une autre representation est de coder en binaire le resultat de la multiplication par 10^9, pour avoir 0x0000007A1A985140.

En base 2^32, tu vas avoir 0x0000020C.6EA4A8C1 mais ce n'est pas une representation exacte, meme si c'est une representation plus precise que les representations decimales ci-dessus (en ce sens que l'intervalle entre deux nombres representables est plus petit).

Comme note historique, Ada83 avait des nombres en virgule fixe dont on donnait simplement la precision, et le langage permettait aux simplementation d'utiliser une precision superieure. Pour repondre aux demandes de ceux qui voulait specifier une resolution decimale, Ada95 a introduit des nombres en virgule fixe decimaux (si on demande 9 chiffres, on aura generalement la 3ieme representation que j'ai donnee).

[Mac LAK]

Virgule fixe décimale, deux chiffres après la virgule: On stocke la valeur bêtement multipliée par 100, 1.3 est stocké en tant que 130.

C'est quasiment ce que j'utilise, la différence étant sur le principe de propagation des retenues.

Sur un exemple à "seulement" 2x32 bits, autant multiplier directement et se passer de la normalisation, effectivement... Voire prendre directement un entier 64 bits.
Si par contre tu as besoin de beaucoup plus de précision, et que tu prends 3 ou 4 entiers 32 bits pour chaque côté de la virgule, tu ne pourras de toutes façons pas échapper à la propagation des retenues, et donc à la normalisation. Là, on arrive plutôt dans le domaine de librairies comme GMP et consort, d'ailleurs.

Mon probleme est que tu presentes comme valables pour toutes les variantes des virgules fixes des caracteristiques qui ne sont presentes que pour certaines d'entre elles, et qui sont presentes aussi avec certains formats de virgule flottante.

Le mien est que, par défaut, "flottant" en C/C++ (et dans beaucoup d'autres langages d'ailleurs) veut dire "IEEE-754" et "appel direct du FPU". C'est normé, contrairement à des formats de stockage plus exotiques (comme la virgule fixe) qui sont intrinsèquement "libres" de faire ce qu'ils veulent.

[screetch]

certes. pour le probleme de l'utilisateur initial cependant, c'est seulement un probleme de base; en base 10 les resultats seront plus précis, simplement puisqu'ils sont entrés par défaut en base 10 (vu que c'est du texte). ansi on est sur que 1.2 + 3.4 = 4.6

[la_tupac]

Et pourquoi pas en stdio. (vive le c)
genre:

Code :

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

1
2
3
char *nb_chr = "10.2";
float nb_flt;
sscanf(nb_chr, "%f", &nb_flt);

Bien sur faut pas avoir peur des warnings

[Invité]

certes. pour le probleme de l'utilisateur initial cependant, c'est seulement un probleme de base; en base 10 les resultats seront plus précis, simplement puisqu'ils sont entrés par défaut en base 10 (vu que c'est du texte). ansi on est sur que 1.2 + 3.4 = 4.6

Dans un cas comme celui là (avec des nombres pas trop grands, un nombre fixe et peu élevé de décimales, et juste des additions et des soustrations) je ne connais pas de machine qui donnerait un résultat faux à cause de la représentation binaire. En gros, toutes les machines savent arrondir les flottants, tant qu'elles travaillent avec des nombres pas trop petits.

Le problème se pose quand on commence à manipuler des nombres d'ordre de grandeur différents, ou voisins des minimaux représentables. Dans ce cas, les flottants permettent de mieux fonctionner que les entiers (les "virgules fixes", ce sont des entiers, obtenus en multipliant pas une puissance, et en arrondissant), parce qu'ils gèrent les puissances. Les flottants résisteront donc mieux à des opérations qui modifient l'ordre de grandeur des nombres (comme les multiplications et les divisions), mais ils se comporteront tout aussi mal si on ajoute des nombres dont les ordres de grandeurs diffèrent de la taille de la mantisse (ou si on soustrait des nombres très voisins).

Pour moi, le seul intérêt de la virgule fixe, c'est une amélioration de la vitesse de calcul et de la compacité du stockage quand on travaille sur des nombres garantis compris dans un intervalle. Par exemple, avec des probas (comprises entre 0 et 1), les representer comme des entiers non signés permet d'avoir une précision de 32 bits (soit plus de 9 chiffres significatifs, là ou les float n'ont que 23 bits de précision, soit 7 chiffres). Il faut alors gérer les arrondis (mais en base 2, c'est extrèmement facile). C'est encore plus spectaculaire sur des précisions plus faibles, en 256eme on passe sur un octet par chiffre, soit quatre fois moins qu'un float... (et une précision de 1/256 soit 0,005, c'est souvent suffisant)

Le défaut, c'est qu'il faut être *certain* qu'on ne sort jamais de l'intervalle. Ca marche pour les probas, je me méfie du reste...

Dans le même ordre d'idée, on pourrait gérer les nombres sous forme de fractions. Il faut alors des "règles d'approximation" quand le numérateur ou le dénominateur dépassent la taille maximale autorisée, Ce n'est pas très simple, mais ca garantit une représentation parfaite... des fractions... (ben oui forcément), et on peut avoir des précisions assez grandes (par exemple sur des fractions normalisées dont les dénominateurs font 32 bits, on peut avoir, vers le milieu de l'intervalle, des précisions bien meilleures que 32 bits: 1/2-1/3 ca fait 1/6...) Mais ca devient vite compliqué et lent, les fractions...

Mais de toutes façon, la solution aux problèmes d'approximation ne peut venir que des algos. Les cas où l'on a réellement besoin d'une précision très importante (au delà des double ou des long double) sont extrèmement rares.

En fait, les nombres à grande précision sont très souvent (mal) utilisés dans des cas ou l'amélioration de l'algorithme permettrait d'éviter une opération susceptible aux erreurs d'arrondi (typiquement, la soustraction de deux nombres très proches)... Curieusement, ca intervient dans plein de formules de base (de l'équation du second degré, à l'interpolation de Lagrange, en passant par les calculs de séries trigonométriques et de gradients/pivots)

Francois

[screetch]

non c'est faux, mon exemple plus haut est que 1,2 n'a pas une représentation exacte en binaire.

[Invité]

non c'est faux, mon exemple plus haut est que 1,2 n'a pas une représentation exacte en binaire.

La machine travaillera avec une représentation approchée, mais les résultats de tes calculs (par exemple le 1.2 + 3.4 = 4.6 que tu citais en exemple) seront quand même corrects, parce que la machine arrondit correctement...

1/3 n'a de représentation finie (tous les nombres ont une représentation exacte dans toutes les bases) ni en base 2, ni en base 10. Et pourtant, on peut l'utiliser dans des calculs : 1/3 + 1/6, ca donnera bien 1/2, et 3* (1/3) ca donnera bien un, sur toutes les machines que je connais...

Ce que j'essaye de dire, c'est que dans un très grand nombre de cas, la représentation approchée des nombres ne pose aucun problème (heureusement, car c'est comme ca qu'on fait *tous* les calculs, avec ou sans machine). Il y a un petit nombre de cas où il faut savoir ce qu'on fait, c'est tout.

Francois

[screetch]

La machine travaillera avec une représentation approchée, mais les résultats de tes calculs (par exemple le 1.2 + 3.4 = 4.6 que tu citais en exemple) seront quand même corrects, parce que la machine arrondit correctement...

non
http://en.wikipedia.org/wiki/Numerical_stability
c'est un lien a lire, c'est tres important de comprendre ca...

[Invité]

non
http://en.wikipedia.org/wiki/Numerical_stability
c'est un lien a lire, c'est tres important de comprendre ca...

Explique moi alors en quoi l'exemple que tu cites est concerné... Donne un programme minimal dans lequel ton commentaire

en base 10 les resultats seront plus précis, simplement puisqu'ils sont entrés par défaut en base 10 (vu que c'est du texte). ansi on est sur que 1.2 + 3.4 = 4.6

s'appliquerait... (c'est à dire que la somme de ces trois nombres serait différente sur un ordinateur en base 10 et sur un ordinateur en base 2, ou si tu préfères quelque chose qui montrerait sur un ordinateur en base 2 que 1,25+3,5=4,75, mais que 1,2+3,4!=4,6...)?


Le problème de sommations qu'évoque l'exemple cité dans le wiki ne se produira que pour de très grandes sommes, pas dans ton cas

Par ailleurs, le problème de stabilité numérique n'est pas lié à la représentation en binaire, mais au fait que les flottants sont représentés avec une mantisse finie : tu aurais exactement le même avec un ordinateur en base 10, ou avec des nombres représentables dans un système binaire. Le problème, c'est que la taille de la mantisse définit l'écart relatif maximal entre deux termes d'une somme...

En ce sens, ton commentaire

non c'est faux, mon exemple plus haut est que 1,2 n'a pas une représentation exacte en binaire.

N'a pas grand chose à voir avec le sujet du wiki...



Maintenant, je ne recommenderais pas ce wiki. L'exemple qu'ils donnent n'est pas très futé: un ordinateur à deux chiffres de précision, ca s'appelle un boulier, et sommer 100 nombres sur un ordinateur à 2 décimales, ce n'est pas un bon exemple de stabilité numérique (je pense que pas mal de spécialistes considéreraient même que ca n'a rien à voir), tout au plus une question d'arrondi.

Mais surtout, la "solution" qu'ils proposent est ridicule. Ils disent :

"A stable algorithm would first sort the array by the absolute values of the elements in ascending order. This ensures that the numbers closest to zero will be taken into consideration first."

En gros, ils proposent de remplacent une somme (opération O(n) ) par un tri (O(nlg(n) ). Et leur méthode n'est même pas optimale : si le tableau consiste en trois chiffres 1e8 -1e8 et 1.0e-20, ils suggèrent d'ajouter 1e-20+1e-8-1e8... et ca, ca donne zéro.

Sur le sujet, tu peux lire ça
http://www.ddj.com/cpp/184403224

et si tu veux absolument du wiki
http://en.wikipedia.org/wiki/Kahan_summation_algorithm
pour un algorithme simple (et plus rapide que la solution proposé par le wiki que tu cites... sur des gros tableaux, effectuer un tri avant une somme, c'est juste inepte).

Soit dit en passant, on peut faire bien mieux que Kahan, en sommant séparément les nombres de magnitude comparable (sommation en cascade).


Mais, une fois de plus, ça n'a rien à voir avec la représentation en base 2.

Francois

[screetch]

non le but du wikipedia en l'occurrence c'etait de montrer que le nombre représentable qui est la meilleure approximation de la somme de deux nombres n'est pas la somme des nombres representables les plus proches.

en binaire on ne peut pas representer correctement 1,2
mais seulement 1,19999998 ou un truc du genre
et apres seulement 5 additions (1,2+1,2+1,2+1,2+1,2) on a déjà une erreur 5 fois supérieure a ce qu'on avait au départ.

Cette erreur initiale est due intégralement au fait que les nombres initiaux sont convertis en binaire avec pertes. si on avait gardé la représentation décimale, quelle que soit la précision des nombres (au moins 3 pour l'exemple plus haut, ce qui est faible) alors la suite d'addition n'aurait conduit a aucune erreur.

Ensuite, il faut rester un peu collé au sujet et ne pas trop divaguer; un ordinateur en base 10 aurait les memes défauts qu'un ordinateur en base 2, mais dans le cas qui nous interesse ici, a savoir le topic lancé par le premier intervenant les opérations effectuées sont des additions, sur des nombres entrés au clavier en base 10.

[Jean-Marc.Bourguet]

Explique moi alors en quoi l'exemple que tu cites est concerné... Donne un programme minimal dans lequel ton commentaire



s'appliquerait... (c'est à dire que la somme de ces trois nombres serait différente sur un ordinateur en base 10 et sur un ordinateur en base 2, ou si tu préfères quelque chose qui montrerait sur un ordinateur en base 2 que 1,25+3,5=4,75, mais que 1,2+3,4!=4,6...)?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
    int i;
    double d1 = 0.1;
    double d2 = 0.2;
    double d3 = 0.3;
 
    std::cout << d3-(d2+d1) << std::endl;
    return 0;
}

Code :

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

1
2
3
$ g++ -msse2 -mfpmath=sse fp.cxx
$ ./a.out
-5.55112e-17

(-msse2 -mfpmath=sse pour éviter le très fameux http://gcc.gnu.org/bugzilla/show_bug.cgi?id=323).

[Invité]

non le but du wikipedia en l'occurrence c'etait de montrer que le nombre représentable qui est la meilleure approximation de la somme de deux nombres n'est pas la somme des nombres representables les plus proches.

Je viens de relire ce wiki, et j'ai l'impression que tu fais erreur. Ce dont ils semblent parler, c'est des erreurs liées aux approximations discrètes en calcul numérique. Très précisément, les difficultés qu'on rencontre quand on résout des équations par des méthodes discrètes (éléments finis ou méthodes itératives). Les concepts d'erreur avant et arrière proviennent de ces domaines.

Mais les différents rédacteurs de cette entrée ne semblent pas d'accord sur le sujet. L'exemple donné parle des erreurs d'arrondi (round off error en anglais), et est plus confusant qu'autre chose. La discussion porte trace de ce débat...

Sur le sujet de la stabilité, celui là est un peu mieux (mais très général)
http://en.wikipedia.org/wiki/Numerical_analysis

Sur les arrondis et les flottants, celui là http://en.wikipedia.org/wiki/Floating_point

en binaire on ne peut pas representer correctement 1,2
mais seulement 1,19999998 ou un truc du genre
et apres seulement 5 additions (1,2+1,2+1,2+1,2+1,2) on a déjà une erreur 5 fois supérieure a ce qu'on avait au départ.

Mais ces erreurs seront éliminées par l'arrondi dans tout programme normalement constitué. Simplement parce le "quantum" d'erreur est très faible (vs la précision demandée sur le calcul).

Par ailleurs, sauf cas très particuliers, les erreurs de représentation sont aléatoirement réparties. Elles vont donc avoir tendance à se compenser, dès qu'on sera sur des "vraies" sommes de nombres différents, et d'ordres de grandeur comparables. Et là, c'est la loi normale qui joue (moyenne nulle, écart type en racine du nombre de termes).


Et je crois coller là à la question d'origine: on parle d'addition de nombres décimaux, de précision assez faible (un ou deux chiffres après la virgule).

A moins d'en faire un *très* grand nombre, ces calculs seront insensibles à la représentation, à cause de l'arrondi final.


C'est d'ailleurs la première phrase de ma première intervention sur ce fil...

Dans un cas comme celui là (avec des nombres pas trop grands, un nombre fixe et peu élevé de décimales, et juste des additions et des soustrations) je ne connais pas de machine qui donnerait un résultat faux à cause de la représentation binaire. En gros, toutes les machines savent arrondir les flottants, tant qu'elles travaillent avec des nombres pas trop petits.

Francois

[screetch]

si tu veux.