Discussion :

[mangeclous]

Bonjour,

Un problème classique en soit mais bon, je n'arrive pas à me
convaincre d'un bon test.
Je veux faire une comparaison a == b ou a et b sont des doubles.
J'ai une source mais de 70 pages à ce sujet what every computer
scientist should know...
existe-t-il une version plus courte ? où une autre source ?

J'aimerai pouvoir répondre à la question
si j'ai obtenu 'a' à partir de 100 opérations et 'b' à partir de 847 opérations
élementaires quel test faire pour a == b
bien sur en fonction de la base et de la précision.

[Joel F]

http://floating-point-gui.de/

meme si la lecure du Goldberg est impérative. 70 pages c'est pas la mort

[ram-0000]

quel test faire pour a == b

Sur des flottants ou des double, il faut faire

Code :

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

if(a - b <= epsilon)

avec epsilon la valeur de ta précision de test.

Attention, il faut que a soit plus grand que b, sinon, il faut inverser le test.

[mangeclous]

http://floating-point-gui.de/

meme si la lecure du Goldberg est impérative. 70 pages c'est pas la mort

n'est pas impérative ?
70 pages c'est pas la mort, si quand même si tu veux comprendre le sujet
sérieusement ça prend facile 10 min par pages vu qu'il y a l'air d'avoir du contenu dans ce papier, j'ai envie de le lire mais j'ai un peu envie de déblayer le terrain.

ram-0000
c'est un peu plus compliqué que ça, ma problèmatique est assez général
j'ai
a = f(....)
et
b = g(.....)
je sais que a est obtenu à partir de N opérations élémentaires
et b à partir de M élémentaires
quel test est raisonnable pour a == b
ça doit être tout de même indépendant de l'ordre de a et b
donc en utilisant fabs mais bon c'est plutôt le choix du epsilon
qui m'intéresse en l'occurence.
Il faut regarder l'erreur relative aussi probablement, enfin je ne suis plus sûr
de rien.

[mangeclous]

http://floating-point-gui.de/

meme si la lecure du Goldberg est impérative. 70 pages c'est pas la mort

Pour citer ton site

"The article What Every Computer Scientist Should Know About Floating-Point Arithmetic gives a detailed introduction, and served as an inspiration for creating this website, mainly due to being a bit too detailed and intimidating to programmers without a scientific background."

[bacelar]

Le plus simple, ne pas utilisez de flottant.
Utilisez des bibliothèques de calcul symbolique.

[Aleph69]

Bonjour,

en général, il faut faire un test en valeur absolue sur la différence entre les flottants, relativement à l'échelle de grandeur des flottants en question.

Le test proposé dans la faq est très bien :
http://cpp.developpez.com/faq/cpp/?p...ions_flottants

Par contre, il faut bien distinguer ce type de test d'un test d'erreur.

Remarque : le nombre d'opérations effectuées en amont pour obtenir a et b n'a pas réellement de sens. Il faut plutôt s'intéresser à la propagation des erreurs d'approximation dans vos calculs. Si vous comptez analyser votre algorithme, il faut vous tourner vers l'arithmétique flottante. Dans ce cas, je vous recommande la lecture du livre "The algebraic eigenvalue problem" de Wilkinson et celle du livre "Accuracy and stability of numerical algorithms" de Higham. Si votre problème concerne un algorithme en particulier, je peux éventuellement vous diriger vers des travaux plus précis.

[mangeclous]

le sujet s'avère beaucoup plus ardu que prévu...

La réponse de la FAQ est pas mal mais bon, le fameux epsilon est un epsilon
local(valable au voisinage de 1) donc c'est ennuyeux pour moi.

ça fait plusieurs fois que je tombe face à ce pb et j'aurai aimé une règle à la
louche(rule of thumbs).
moi mon problème, c'est j'ai un a = f(...)
b = g(...) et mathématiquement sur le papier en cas de calcul exact, a = b
je dois faire ce test en Cpp.
Je pense que le nombre d'opérations pour obtenir a et b est important pour avoir un majorant de l'erreur sur a-b qui permettrait de choisir le epsilon sciemment et non en disant que "statistiquement les erreurs se compensent".

Je crois même que l'explosion du premier Ariane 5 est lié à un pb de ce type, je n'envoie pas une fusée sur la lune mais peut-être demain !

[Aleph69]

Bonjour,

La réponse de la FAQ est pas mal mais bon, le fameux epsilon est un epsilon
local(valable au voisinage de 1) donc c'est ennuyeux pour moi.

Si tu ne veux pas utiliser le epsilon, tu compares juste avec la valeur max et une tolérance :

Code :

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

1
2
3
4
 
bool areEqual(double a,double b)
{
    return std::abs(b-a)<=tol*std::max(std::abs(a),std::abs(b));

moi mon problème, c'est j'ai un a = f(...)
b = g(...) et mathématiquement sur le papier en cas de calcul exact, a = b
je dois faire ce test en Cpp.

Si tu n'es pas en mesure de déterminer si ton algorithme est stable vers l'arrière (forward stable) et si tu n'as aucune propriété de convergence, tu ne peux faire un test exact du type

Code :

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

1
2
 
if (a==b)

Je pense que le nombre d'opérations pour obtenir a et b est important pour avoir un majorant de l'erreur sur a-b qui permettrait de choisir le epsilon sciemment et non en disant que "statistiquement les erreurs se compensent".

Personne n'a dit que les erreurs se compensent statistiquement.
Certes, le nombre d'opérations apparaît dans les majorations d'erreur, tout comme l'erreur d'arrondi commise par ta machine sur les opérations élémentaires, mais ce qu'il est surtout important de voir c'est le conditionnement de ton problème et les éventuels autres facteurs liés à tes données.

Note d'ailleurs que si a et b ne sont pas des scalaires, deux types d'analyse d'erreur sont possibles, l'une par norme (normwise) et l'autre par composante (componentwise).

Tu devrais peut-être commencer par décrire ton algorithme pour qu'on puisse t'orienter vers un choix judicieux de test.

[Invité]

Bonjour

J'aimerai pouvoir répondre à la question
si j'ai obtenu 'a' à partir de 100 opérations et 'b' à partir de 847 opérations
élementaires quel test faire pour a == b
bien sur en fonction de la base et de la précision.

On peut répondre de la façon suivante.
Soit e l'erreur (c'est à dire imprécision) commise sur une opération
Le terme erreur est à prendre au sens de la théorie des erreurs, loi de Gauss
Alors l'erreur sur a est e.racine(100)
l'erreur sur b est e.racine(847).

Il ne sera peut-être pas très facile d'évaluer e, mais le document cité peut être lu en diagonale et les "théorèmes" sont bien faits.

Par ailleurs, des essais ont été faits pour évaluer cette erreur, je ne peux pas dire qu'ils aient été concluants.
Je pense que chaque cas est un cas particulier qu'il faut étudier avec soin, et je ne suis pas sûr que l'on puisse garantir à 100% la réussite des tests.

[mangeclous]

Aleph69
1)
Même si j'utilise la tolérance, il reste le problème de fond:
comment choisir la tol sciemment ? c'est un choix empirique ou pas?
2)
Je ne sais pas ce qu'est un algo stable vers l'arrière. Ca fait plusieurs
fois que je tombe sur cette problématique et j'aurai aimé la comprendre
bien
3)
Personne n'a dit que les erreurs se compansent il est vrai, c'est juste
un argument pipo que l'on m'a donné plusieurs fois(pas ici je précise)
4)
pour l'algo. par exemple une PDE.
Je veux faire des tests où les coef de diffusion, etc... sont constant et où j'ai une solution analytique. Quelle erreur supplémentaire apporte la représentation des réels en machine à l'erreur de discrétisation?


Apparemment chaque cas est un cas particulier, je garderai quand même
le résultat de marche aléatoire de Pierre mais 'e' reste difficile à évaluer

Quel argument réellement scientifiquement fondé permet de relâcher la
condition sur la tolérance ?

Comment je peux savoir avec quelle précision est représenté un double sur ma machine? taille de la mantisse et exposant
si je pose v = 0.2; quand je débugue v "vaut déjà" 0.2 + 1e-17 quand je l'affiche dans la watch list
ça veut dire que chaque double est réprésenté à 1e-17(en valeur relative) ?

[JolyLoic]

Peut-être trouveras-tu des outils t'aidant à observer la stabilité de ton algorithme sur http://www.boost.org/doc/libs/1_44_0...c/interval.htm

[Invité]

Bonjour,

Comment je peux savoir avec quelle précision est représenté un double sur ma machine? taille de la mantisse et exposant
si je pose v = 0.2; quand je débugue v "vaut déjà" 0.2 + 1e-17 quand je l'affiche dans la watch list
ça veut dire que chaque double est réprésenté à 1e-17(en valeur relative) ?

Les normes ANSI et IEEE précisent ce genre de chose.
Sur mon bouquin, mais je pense sur toutes les machines PC 32 bits,un float a une précision de 7 chijjres significatifs, un double de 15 chiffres, un long double 80 bits) de 19 chiffres.

Pour fixer la valeur de e. On peut le faire mathématiquement, c'est à dire avoir un résultat statistiquement vrai, en faisant un petit traitement d'application de la théorie des erreurs, loi de GAUSS.
Le principe général est simple, on fait un certain nombre d'essais, par exemple 100 ou 1000, et on calcule pour chaque essai l'écart à la valeur vraie (1) ou à la moyenne, suivant le cas. Puis on classe ces écarts en 10 paquets. La répartition des nombre d'écarts dans les paquets est parfaitement connue.
Par exemple, pour évaluer les résultats sur un calcul en float, on peut considérer que la "valeur vraie" est obtenue pas le même calcul en double.

(1) "valeur vraie" a une signification dans la théorie des erreurs. (rien à voir avec vraie valeur)

[1337cclean]

en résumé,...

Un ordinateur à la Von Neumann,
ne travail strictement que dans deux paradigmes,
(dans le cadre des mathématiques) ...

1/ représentation discrète d'éléments (ensemble dénombrable fini!) et ne peux donc en aucun cas admettre la représentation de TOUT élément de R (ni C) ou autres, ens. ergodiques, fractals, /etc.

2/ représentation symbolique d'être mathématiques abstraits. (Tout aussi dénombrable...)

ben zut alors

C'est bête, mais on vit dans un e-monde fini.

[Invité]

Bonjour,
Un petit développement explicatif ne serait pas superflu.

[1337cclean]

Bonjour,
Un petit développement explicatif ne serait pas superflu.

C'est contradictoire avec le principe de "résumé".

"Contraposont-donc le sujet"...

La représentation de quelque nombres que ce soit appartennant à quelque ensembles que ce soit est, et reste limitée (Dans une machine concrètement discrète) à des chaines de bits (morceau d'information élémentaire... tient? Eléments fini? ...bref.).

exemple des "nombres réels"... double, float...

[pseudo-real]-BEGIN
Donc pour les nombres "pseudo réels", ce ne sera qu'au mieux une suite finie de bits pour représenter une éventuelle mantisse, puis une autre chaine tout aussi limitée pour représenter un éventuel exposant...
[pseudo-real]-END

impliquent

Un nombre fini d'éléments "pseudo-réels" représentables de la manière décrite, avec pour corollaire que le sous-ensemble des éléments compris entre A et B distincts!, pourtant représentables sur la base mentionnée admet forcément une infinité de nombres réels, voir-même tout simplement décimaux (ensemble D, dénombrable ou "discrèt"), NON REPRESENTABLE selon la méthode finis mentionnée sous [pseudo-real].

J'ajoute que même "du temps" des ordinateurs analogiques (ampli-op, etc.), il étaient absolument impensable de comparer deux signaux AUTREMENT que par relations d'inéquations. [Par ailleurs, la pièce maîtresse des ces ordinateurs était l'ampli-opérationnel, utilisé notamment comme "comparateur",...]

Solution: Travailler sur des marges d'erreur, par exemple la distance entre les deux signaux, soit une valeur absolue de leur différence au voisinage de zéro, non egal à zéro! En lieu et place d'une éventuelle assertion équationnelle concernant deux signaux représenté éléctroniquement, digitalement, analogiquement, physiquement. (Par opposition à des représentations symboliques. Des langages sont conçu pour ça.)

- Comme ce qui semble avoir déjà été énoncé dans ce sujet (epsilon) -



Je me reprends...

en résumé,...

Un ordinateur à la Von Neumann,
ne travail strictement que dans deux paradigmes,
(dans le cadre des mathématiques) ...

1/ représentation discrète d'éléments (ensemble dénombrable fini!) et ne peux donc en aucun cas admettre la représentation de TOUT élément de R (ni C) ou autres, ens. ergodiques, fractals, /etc.

2/ représentation symbolique d'être mathématiques abstraits. (Tout aussi dénombrable...)

ben zut alors

C'est bête, mais on vit dans un e-monde fini.

...à remarquer que ces deux paradigmes n'en font qu'un...
:: La discrètisation de la représentation.


REFS
http://fr.wikipedia.org/wiki/Amplifi...C3%A9rationnel
On y voit clairement une entrée (+) et une entrée (-) comparée analogiquement et amplifiée (gain) en général quelquonque et aussi élevé que possible.

Conception de calculs numériques selon une " Fonction ULP(x) "...
http://en.wikipedia.org/wiki/Unit_in_the_last_place
- à étudier -

[Aleph69]

Bonjour mangeclous,

désolé, j'ai complètement oublié de répondre à tes questions.

1)
Même si j'utilise la tolérance, il reste le problème de fond:
comment choisir la tol sciemment ? c'est un choix empirique ou pas?

Le choix de la tolérance est guidé par ce que te dit l'analyse d'erreur de ton algorithme. Si tu sais borner l'erreur de calcul (relative!) que tu commets à la sortie de ton algorithme, alors ça te permet de choisir une tolérance qui a un sens. Par exemple, si ton erreur est majorée par 1E-6, alors tu sais qu'en mettant une tolérance à 1E-5 tu passeras dans ton test d'erreur. C'est comme cela qu'on fait dans les stratégies de monitoring utilisées dans la résolution des équations aux dérivées ordinaires par exemple.

2)
Je ne sais pas ce qu'est un algo stable vers l'arrière. Ca fait plusieurs
fois que je tombe sur cette problématique et j'aurai aimé la comprendre
bien

Je te propose de lire ceci, ce sera mieux écrit que ce que je peux te proposer :
http://en.wikipedia.org/wiki/Numerical_stability

3)
Personne n'a dit que les erreurs se compansent il est vrai, c'est juste
un argument pipo que l'on m'a donné plusieurs fois(pas ici je précise)

En fait, on ne peut rien dire a priori car les erreurs peuvent localement se compenser! Mais il n'y a rien de statistique là-dedans, c'est purement informatique.

4)
pour l'algo. par exemple une PDE.
Je veux faire des tests où les coef de diffusion, etc... sont constant et où j'ai une solution analytique. Quelle erreur supplémentaire apporte la représentation des réels en machine à l'erreur de discrétisation?

L'erreur de calcul dépend de la manière dont tu implémentes ton algorithme.
Jette un oeil à ça, tu vas comprendre : http://en.wikipedia.org/wiki/Algorit...ating_variance

Ta discrétisation borne supérieurement ton erreur d'approximation. Par exemple, avec un schéma aux différences finies d'ordre 2 sur un segment subdivisé en un nombre fini de sous-segments tous de longueur h, tu sais que ton erreur de discrétisation est en O(h^2).
En imaginant que dans ton cas, cette borne soit atteinte en précision exacte, alors en précision finie tu ne pourras pas faire mieux mais tu pourras faire bien pire!

Ce qui va influer sur l'erreur de calcul c'est trois choses :
1. la précision de la machine
2. la stabilité vers l'arrière de l'algorithme
3. le conditionnement de ton problème

Grossièrement, tu as erreur_calcul = erreur_arrière*conditionnement.
L'erreur vers l'arrière dépend de la précision machine et de ton implémentation.
Le conditionnement dépend uniquement de tes données.
Si ton problème est très mal conditionné, alors une petite erreur vers l'arrière peut entraîner une grande erreur au final!
Dans ton cas, le conditionnement dépend des coefficients de ton système d'équations aux dérivées partielles et des sources de ton problème.

Apparemment chaque cas est un cas particulier, je garderai quand même
le résultat de marche aléatoire de Pierre mais 'e' reste difficile à évaluer

Non, tu peux oublier ce résultat.
Quiconque te donne une erreur sans donner l'implémentation de son algorithme se trompe forcément, au moins dans sa démarche.
Si tu ne connais pas l'implémentation, tu peux seulement fournir une erreur en précision exacte, comme ton erreur de discrétisation par exemple.

Quel argument réellement scientifiquement fondé permet de relâcher la
condition sur la tolérance ?

La seule manière d'argumenter est de faire une analyse d'erreur pour borner ton erreur de calcul. Cette borne va dépendre de tes données et la précision machine. Une fois ton erreur encadrée, tu sais à quoi t'en tenir pour choisir la tolérance.

Comment je peux savoir avec quelle précision est représenté un double sur ma machine? taille de la mantisse et exposant
si je pose v = 0.2; quand je débugue v "vaut déjà" 0.2 + 1e-17 quand je l'affiche dans la watch list
ça veut dire que chaque double est réprésenté à 1e-17(en valeur relative) ?

Ca dépend du langage de la machine et de la machine.
En C++, je n'ai jamais regardé quelles fonctions utiliser pour le faire mais il faut chercher du côté du epsilon qui apparaît dans le lien vers la faq que je t'ai donné. A priori, en double, ta précision doit être à peu près égale 2,2E-16 si ta machine est standard, respecte la norme IEEE, et si j'ai bonne mémoire! ^^

[1337cclean]

à priori, un calcul numérique sur du float, double, vers laquel ont est intéressé à une éventuelle convergence vers un nombre donné, on peut aisément rendre paresseux la gestion de bornes (min,max) ave min<max et x dans [min,max] et lorsque l'algorithme voit ses bornes "stagner" (donc ne plus être "ajustées") ALORS on est dans une "convergence" dans cette catégorie d'ensemble discrèts,

et par nature de l'algorithme de cette sorte de mis-en-sandwich artificielle, donnera naturellement (quelque soit la représentation, 16bits, 32bits, 64bits...) le signal symbolique d'un arrêt discrèt de cette convergence.
[à considérer évidemment aussi une éventuelle divergence, auquel cas les bornes ne cesseront de " s'éloigner "...]

:: min et max étant conditionnées par la distance entre une valeur supposée d'un éventuel arrêt recherché et la valeur calculée par l'algorithme en étude...

Attention aux valeurs "hors champs" de toute les opérations mise-en-jeu,... division par zéro, logarithmes de valeurs négatives pas dans "real", arctan, ...

:: Ceci est une proposition au pif
:: Proposition ayant l'avantage d'être INDEPENDANTE de lectures fastidieuses de normes, sauf si c'est l'objet d'un cours lié aux méthodes numériques...

[Aleph69]

à priori, un calcul numérique sur du float, double, vers laquel ont est intéressé à une éventuelle convergence vers un nombre donné, on peut aisément rendre paresseux la gestion de bornes (min,max) ave min<max et x dans [min,max] et lorsque l'algorithme voit ses bornes "stagner" (donc ne plus être "ajustées") ALORS on est dans une "convergence" dans cette catégorie d'ensemble discrèts,

C'est déconseillé : en précision finie, un algorithme peut se mettre à stagner pendant un nombre important d'itérations sans qu'il y ait convergence. C'est par exemple le cas de GMRES pour la résolution des systèmes linéaires.

[1337cclean]

C'est déconseillé : en précision finie, un algorithme peut se mettre à stagner pendant un nombre important d'itérations sans qu'il y ait convergence. C'est par exemple le cas de GMRES pour la résolution des systèmes linéaires.

Dans ce cas j'ajouterais volontier à nouveau une lazzy-method identique à celle que je mentionne [brouillonnement], mais cette fois-ci bornées sur les itérations "stagnantes"|"non stagnantes" ce qui revient à éviter une éventuelle étude d'une fonction ulp(x), par nature dépendante de la plateforme,... ce que je recherche dans ma proposition orientée laboratoire d'étude numérique; Domaine très ancien et peu rencontré dans ma courte carrière. Je me suis laissé orienté linguistique et calculs symbolique, bienque je m'intéresse toujours à ce qui se fait aujourd'hui en mathématique, avec cette "informatique", science qui n'existait pour ainsi dire qu'en laboratoire, lorsque j'eusse commencé à faire de l'électronique, puis de l'informatique. (internet n'existait pas encore à l'échel publique, ni l'ordinateur de table @home...)

:: Pour des calculs d'algèbre linéaire, matriciels, bien que les problèmes mentionnés soient les mêmes concernant la précision, la NASA (par exemple) utilise encore plutôt le FORTRAN que le C++, mais si on est sous gcc, à priori on change de langage mais pas la problèmatique lié à la-dites précision.
- intuitif -