Faire des calculs flottants précis

Version imprimable

14/08/2011, 01h20
shared_ptr

Faire des calculs flottants précis

Bonjour,

Je cherche à écrire un petit programme destiné à faire des calculs de fiabilité à partir de la description d'un système (fournit sous forme d'un fichier type xml). J'ai déjà écrit la base du logiciel, sauf que quand je le fait tourner afin de tester, je suis plutôt déçu de la précision des résultats obtenus : il n'est pas rare que la somme de 3 variables initialisées à 1e-7 donne 2.997e-7. Mais cela, bien sûr, je m'en doutais un peu.

Aussi je me demandais quelle était la meilleure solution pour faire des calculs flottants (sur des doubles en l'occurence) précis en C++.

Existe-il des librairies portables qui fassent autorité dans le domaine ? Faut il que je programme moi même une petite lib vu que ça peut être simple (fixed point arithmetic par exemple) ?

Merci de me faire partager vos opinions/expériences sur le sujet :D
14/08/2011, 01h47
Aleph69

Bonjour,

la précision des calculs dépend de la précision machine, de l'algorithme (stabilité) et des données (conditionnement). Il faut faire une analyse mathématique/numérique sérieuse de ton algorithme pour déterminer quoi faire pour améliorer la précision de tes résultats (voir backward/forward error/analysis sur google, ou mieux le livre de Nigham dont le titre est "accuracy and stability of numerical algorithms" si j'ai bonne mémoire).

Il existe des bibliothèques faisant autorité dans certains domaines au moins. L'exemple le plus connu étant LAPACK pour l'algèbre linéaire.

Il ne faut pas regarder ce qui se passe localement (somme des trois variables initialisées) mais seulement l'erreur globale sur la quantité qui t'intéresse. La raison est que les erreurs d'arrondi peuvent s'annuler, c'est-à-dire que l'erreur sur la somme de tes trois variables peut être compensée plus tard dans l'algorithme par d'autres erreurs d'arrondi.

A noter qu'il existe des bibliothèques permettant de faire des calculs au-delà de la précision machine. Deux problèmes à ce genre de solution : premièrement, les calculs sont plus lents; deuxièmement, si tu as un problème important de conditionnement, il te faudra calculer très très très très très très (j'en ai mis assez?) précisément (donc ça sera très très très très très très lent).

En revanche, si tu as préalablement pris soin d'analyser le comportement numérique de ton algorithme, tu pourras utiliser ces bibliothèques pour faire des calculs en précision mixte : en gros, faire des calculs en précision double sauf à des endroits bien identifiés où tu feras des calculs en quadruple (ou plus) précision pour maintenir une précision suffisante sans ralentir trop ton code.

EDIT : tu peux regarder cette page sur le calcul de la variance d'un échantillon. C'est un exemple historique important et la présentation wilkipedia n'est pas trop mal : http://en.wikipedia.org/wiki/Algorit...ating_variance
14/08/2011, 08h53
Joel F

y a pas de miracle :

- passez a double pour augmenter la dynamique et la precision absolu dans les zones classiques
- ecrire des algos propres ou les erreurs d'arrondis sont maitrisees. Je conseille CADNA pour analyser les algos deja ecrit
- Si la precision est toujours manquante : GMP ou MPFR fourniront ce qu'il faut au detriment du temps de calcul.

D'experience, la reecriture des algorithmes est souvent le plus payant mais necessite de bien savoir ce qui se passe au niveau machine donc qqs lecture :

Une intro simple:
http://floating-point-gui.de/

et le papier de Goldberg :
http://download.oracle.com/docs/cd/E..._goldberg.html
14/08/2011, 16h57
loufoque

Sur x86, attention à la précision étendue propre au FPU, qui ne sera pas garantie quand on passe par la mémoire ou par les unités SSE ou AVX.
15/08/2011, 01h29
shared_ptr

Bonjour à tous et merci pour vos différents éléments de réponse !

J'ai parcouru les différents liens et j'y ai vu pas mal de choses intéressantes.
http://floating-point-gui.de/ m'a fait sourire d'ailleurs puisque son introduction :

Citation:

So you’ve written some absurdly simple code, say for example:

0.1 + 0.2

and got a really unexpected result:

0.30000000000000004

Maybe you asked for help on some forum and got pointed to a long article with lots of formulas that didn’t seem to help with your problem.

Correspond tout à fait à ce qui m'est arrivé :D

Je vois un peu plus clair à présent sur les différentes méthodes qui peuvent s'offrir à moi pour améliorer la précision de mes calculs (qui étaient déjà effectués sur des double btw)

Par contre, concernant l'aspect "stabilité des algos", j'ai un peu de mal à voir comment le mettre en oeuvre sur ce que j'implémente.

Autant je conçois bien (je retrouve même en fait vu que j'avais déjà vu ce genre de truc en prépa) comment cette démarche peut-être mise en oeuvre pour des algos type calcul de la variance (cf l'exemple wikipedia que vous donnez), pour lequel la fonction de calcul est parfaitement définie une fois pour toute, autant j'ai plus de mal avec ce que je souhaite faire : des calculs de fiabilité qui vont dépendre énormément de la topologie du système étudié (composants présents et façon dont ils sont agencés). Sur certains systèmes, les calculs (qui traduisent l'existence de redondances passives ou actives, de plans de protection, d'action de controles-commande, ...) seront effectué d'une certaine façon, qui peut être assez différents d'autres systèmes (même si les composants sont globalement les mêmes). Dénombrer toutes ces configurations, et donc tous les calculs possibles n'est pas envisageable.

Raison pour laquelle je cherchais une solution un peu générique : si j'obtiens des résultats type 2.997e-7 en effectuant 3 additions, quel crédit pourrais-je donner aux valeurs obtenus suite aux calculs effectués sur l'ensemble de mon système ?

J'ai fait quelques essais d'implémentation sous R, et j'obtiens des résultats beaucoup plus précis comme ont pouvait s'y attendre. J'imagine qu'il en serait de même avec Matlab voire Excel (VBA).

Toutefois compte tenu de la taille des systèmes qui peuvent être considérés, couplé au fait que C++ est compilé et Matlab interprété, et compte tenu du fait que les algos mis en oeuvre reposent essentiellement sur des parcours d'arbres à l'aide de fonctions récursives, il me semble plus judicieux de conserver le C++ a priori.

Les types décimaux, qui sont notamment abordés dans ton premier lien Joel, peuvent peut être fournir des résultats intéressants (biblio decimal en C#, BigDecimal en Java), mais le site n'aborde pas le cas du C++.
15/08/2011, 09h01
Joel F

Citation:

Envoyé par shared_ptr

Autant je conçois bien (je retrouve même en fait vu que j'avais déjà vu ce genre de truc en prépa) comment cette démarche peut-être mise en oeuvre pour des algos type calcul de la variance (cf l'exemple wikipedia que vous donnez), pour lequel la fonction de calcul est parfaitement définie une fois pour toute, autant j'ai plus de mal avec ce que je souhaite faire : des calculs de fiabilité qui vont dépendre énormément de la topologie du système étudié (composants présents et façon dont ils sont agencés). Sur certains systèmes, les calculs (qui traduisent l'existence de redondances passives ou actives, de plans de protection, d'action de controles-commande, ...) seront effectué d'une certaine façon, qui peut être assez différents d'autres systèmes (même si les composants sont globalement les mêmes). Dénombrer toutes ces configurations, et donc tous les calculs possibles n'est pas envisageable.

Ce n'est pas ce que je te dis de faire ;0

Citation:

Envoyé par shared_ptr

Raison pour laquelle je cherchais une solution un peu générique : si j'obtiens des résultats type 2.997e-7 en effectuant 3 additions, quel crédit pourrais-je donner aux valeurs obtenus suite aux calculs effectués sur l'ensemble de mon système ?

Y a des choses qui marche tout le temps : faire attention a pas ajouter un enorme reels a un tout petit en ordonnant les calculs intermediaires ou en utilisant des algos comme Khan. Regarde CADNA, ca te donnera une idee des problemes qui arrivent et de comment les eliminer.

Citation:

Envoyé par shared_ptr

J'ai fait quelques essais d'implémentation sous R, et j'obtiens des résultats beaucoup plus précis comme ont pouvait s'y attendre. J'imagine qu'il en serait de même avec Matlab voire Excel (VBA).

Non, les fonctions Matlab sont des fonctions C ou FORTRAN derriere donc meme tarifs. Quant a Excel, meme systeme. R fonctionne differemment car il possede un noyeau de calcul symbolique.

Citation:

Envoyé par shared_ptr

Les types décimaux, qui sont notamment abordés dans ton premier lien Joel, peuvent peut être fournir des résultats intéressants (biblio decimal en C#, BigDecimal en Java), mais le site n'aborde pas le cas du C++.

Je repete GMP, MPFR
17/08/2011, 00h25
Aleph69

Citation:

Envoyé par shared_ptr

Autant je conçois bien (je retrouve même en fait vu que j'avais déjà vu ce genre de truc en prépa) comment cette démarche peut-être mise en oeuvre pour des algos type calcul de la variance (cf l'exemple wikipedia que vous donnez), pour lequel la fonction de calcul est parfaitement définie une fois pour toute, autant j'ai plus de mal avec ce que je souhaite faire : des calculs de fiabilité qui vont dépendre énormément de la topologie du système étudié (composants présents et façon dont ils sont agencés). Sur certains systèmes, les calculs (qui traduisent l'existence de redondances passives ou actives, de plans de protection, d'action de controles-commande, ...) seront effectué d'une certaine façon, qui peut être assez différents d'autres systèmes (même si les composants sont globalement les mêmes). Dénombrer toutes ces configurations, et donc tous les calculs possibles n'est pas envisageable.

Il suffit d'écrire ton algorithme proprement puis d'utiliser l'arithmétique flottante pour voir comment se propagent les erreurs de calcul (par des majorations). Il faut que tu regardes le paragraphe "arithmetic model" dans ce lien :
http://en.wikipedia.org/wiki/Machine_epsilon
La première égalité dit simplement qu'on considère qu'une opération binaire entre deux flottants (+,-,*,/) est toujours arrondie de la même manière. Ce n'est pas tout à fait vrai mais cette hypothèse simplificatrice suffit en pratique. La seconde égalité dit exactement la même chose mais en faisant intervenir la précision des calculs (symbolisée par la lettre z). A partir de cette égalité élémentaire, tu peux majorer les erreurs d'arrondi pour les opérations entre vecteurs, matrices, etc. En majorant intelligemment, tu obtiendras une estimation a priori de l'erreur sur les quantités que tu souhaites exploiter en sortie de ton algorithme.

Citation:

Envoyé par shared_ptr

Raison pour laquelle je cherchais une solution un peu générique : si j'obtiens des résultats type 2.997e-7 en effectuant 3 additions, quel crédit pourrais-je donner aux valeurs obtenus suite aux calculs effectués sur l'ensemble de mon système ?

En effectuant une analyse en précision finie de ton algorithme pour obtenir un estimateur a priori des erreurs de calcul, comme expliqué plus haut. Tu peux également, chercher un estimateur a posteriori de l'erreur, mais c'est un peu plus difficile car il faut s'y connaître un peu en analyse fonctionnelle. On trouve sûrement des travaux sur ce point dans ton domaine.

Citation:

Envoyé par shared_ptr

J'ai fait quelques essais d'implémentation sous R, et j'obtiens des résultats beaucoup plus précis comme ont pouvait s'y attendre. J'imagine qu'il en serait de même avec Matlab voire Excel (VBA).

Cela signifie que ton algorithme est moins stable. Sous R/Matlab/Excel, tu vas faire appel à des fonctions élémentaires toutes faites dont tu ne disposes pas en c++ : ce sont les algorithmes correspondants qui font défaut dans ton cas. Tu pourrais écrire de meilleurs algorithmes pour effectuer ces tâches.