OVH Cloud OVH Cloud

Calculs du point de vue de la norme

57 réponses
Avatar
jul
Salut,

Je programme une application qui fait un fort usage des calculs avec
des valeurs d=E9cimales (=E0 virgule) avec les types float ou double. Il
ne me semble pas que ces calculs sont pris directement en charge par
le(s) processeur(s). Ma question est donc la suivante : la norme
impose-t-elle l'identit=E9 des r=E9sultats de calculs entre diff=E9rents
compilateurs ? Si oui, au moyen de quel(s) crit=E8re(s) ?

Je pr=E9cise pour bien me faire comprendre. Il facile d'exiger qu'un
compilateur calcule de mani=E8re correcte sur les entiers (1+1 doit
toujours =EAtre =E9gal =E0 2), ce qui est en soi une garantie
(ext=E9rieure) de l'identit=E9 des r=E9sultats. Mais lorsque le calcul a
lieu sur des nombres d=E9cimaux, le r=E9sultat est souvent arrondi. Il
n'y a pas alors de "r=E9sultat juste" (ex. 1/3 n'a pas d'expression
d=E9cimale finie juste, m=EAme si certaines sont meilleures que
d'autres). Comment sait-on que la mani=E8re de calculer et d'arrondir
sera la m=EAme sur chaque compilateur ?

Merci pour vos =E9claircissements.
Jul.

10 réponses

1 2 3 4 5
Avatar
kanze
kanze wrote:
Sylvain wrote:


[...]
template<typename T> T sumPart(float const* array, size_t size)
{
size = (size_t) sqrt(size);

T result = 0.0;
float const* t = array;
for (size_t k = 0; k < size; ++k){
T inter = 0.0;
for (size_t i = 0; i < size; ++i, ++t)
inter += *t;
result += inter;
}
return result;
}



[...]
Les résultats sur Sparc correspond à peu près à ce que je
m'attends -- on fait mieux que l'algorithme naïf, mais on est
encore derrière les solutions « correctes ». Les résultats sur
PC sont encore plus intéressants -- pourquoi moins de précision
qu'avec la solution naïve ? Ce que je soupçonne (mais je n'ai
pas encore vérifié), c'est que g++ garde la variable
d'accumulation dans un régistre (avec donc la précision
supplémentaire), mais seulement pour la boucle intérieur.


Je le confirme. Dans sumUp (une boucle simple de 0 à size), le
code généré met l'accumulateur (ma variable result) dans un
règistre flottant, et donc maintient la valeur intermédiaire sur
80 bits (dont 64 de mantisse). Dans le code ci-dessus, en
revanche, il n'utilise le règistre flottant que pour la boucle
interieur (la variable inter) -- result reste en mémoire, et
donc sur 32 bits (dont 24 de mantisse).

Comme j'ai dit, je ne suis pas sûr que c'est légal. Mais légal
ou non, c'est ce qu'il fait.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
Jean-Marc Bourguet
Sylvain writes:

tes routines sont intéressantes ! de mon point de vue, elles sont toutes
inadaptées et maladroites (ce n'est pas une provocation!).


En quoi sont-elles inadaptees a l'objectif poursuivi: analyser
l'erreur introduite par differentes manieres de faire la somme
(definie comme etant la difference entre le resultat exact arrondi a
la precision d'un float et le resultat calculer)?

dans tes benchs tu accumules 1.000.000 de valeurs flottantes de type float,
or un float à une précision de 10^-6, en sommer 10^6 va obligeatoirement
faire perdre toute précision de l'élément ajouté par rapport à l'accu
courant - ie va générer un débordement de précision et revient à faire un
inf + epsilon en espérant trouver l'epsilon dans le nouveau résultat.


Je ne comprends pas.

Dans le cadre donne ci-dessus, on peut prouver des bornes superieures
pour l'erreur introduite pour deux des algorithmes (sumPriority,
sumCompensated) qui sont de l'ordre de quelques ULP (si j'ai bonne
memoire, moins d'un ULP pour sumCompensated, autrement dit, une des
valeurs qui encadrent le resultat exact).

template<typename T> T sumPart(float const* array, size_t size)
{
size = (size_t) sqrt(size);

T result = 0.0;
float const* t = array;
for (size_t k = 0; k < size; ++k){
T inter = 0.0;
for (size_t i = 0; i < size; ++i, ++t)
inter += *t;
result += inter;
}
return result;
}

donne également le bon résultat pour un type T float.


Meme principe que sumBinary, mais deux niveaux seulement. Je suis
certain qu'il y a moyen de contruire des jeux de donnees
(vraissemblablement meme avec toutes les valeurs comprises entre 0.5
et 1) pour lequel on a un resultat moins precis que
sumCompensated<float>.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Avatar
jul
1) J'ai manqué de clarté : j'entendais "décimaux" au sens
mathématique (c'est pourquoi j'ai mis "à virgule", bien que ce
ne soit pas si clair que ça). Je n'accorde aucune importance à
la représentation interne du nombre.


Et quel est sa sens mathématique ? Je ne l'ai vu servir que pour
parler de la base de représentation. En mathématique, j'ai
traité surtout des entiers, des rationnels et des réels


Il me semble avoir appris (mais c'est assez loin) qu'il y a un ensembe
D inclus dans Q, celui des nombres réels ou rationnels ayant un
développement décimal fini. Ce sont ces nombres que j'appelle
"décimaux" (peut-être à tort).

2) C'est moins le problème d'identité dans le code (utiliser
== après deux calculs identiques) que celui de garantir la
même sortie entre deux exécutables compilés à partir du même
code source, sachant qu'une faible différence dans le résultat
d'un calcul peut entraîner de grosses différences dans ladite
sortie.


C'est en fait à peu près ce que j'avais compris. Et si tu as lu
mes réponses (ce qui exige un certain effort, je l'avoue), tu
auras compris que la réponse est « pas du tout ». Même avec la
même source, le même compilateur et le même processeur, j'ai
deux résultats différent, selon les options de compilation -- en
gros, tu risques d'avoir des résultats différents entre la
version debug et la version que tu livres.


C'est ce que j'avais cru comprendre, mais là c'est parfaitement clair.
Merci beaucoup.

Jul.


Avatar
Jean-Marc Bourguet
"kanze" writes:

Jean-Marc Bourguet wrote:
"kanze" writes:

Jean-Marc Bourguet wrote:

float et double sont classiquement des nombres en virgule
flottante binaires.


Juste un détail, mais tu n'as pas dû lire les classiques. Sur
l'IBM 1401, ils étaient base 10 (et pour être classique, c'est
une classique), et sur l'architecture la plus « classique »
encore répandue aujourd'hui, ils sont base 16. Ce n'est que sur
les ordinateurs ultra-moderne et avant garde, dont la conception
de l'architecture rémonte à moins de quarante ans, où on peut
être sûr de trouver le binaire.


J'ai dit float et double, en parlant des types C++. Tu as vu
une implementation de C++ ou float et double n'etaient pas
binaires?


Oui. La plus classique de tous (en ce qui concerne le processeur
en général -- c'est vrai qu'il a mis du temps à se mettre à
C/C++), l'IBM 390.


C'est une architecture classique, ce n'est pas une implementation de C
ou de C++ classique.

Quant a l'histoire, si j'ai bien compris, a cette epoque les
machines etaient decimales ou binaires; celles destinees aux
charges "commerciales" -- remplacement des tabulatrices --
decimales, celles destinees aux charges "scientifiques" --
calculs -- binaires. Donc j'ai l'impression que les flottants
dans leur domaine d'utilisation naturel sont classiquement
binaires.


Plus ou moins. IBM, au moins, a toujours été une exception, et
l'architecture 360 offrait à la fois l'arithmetique décimal (BCD)
pour les applications commerciales, et des virgules flottants
hexadécimaux pour les calculs numériques (et se vendaient bien dans
les deux domaines).


IBM 360, c'est pour moi le moment ou la separation entre machine
commerciale et machine scientifique commence a s'estomper d'un point
de vue architecturale. Apres, il n'y a quasiment plus de machines
decimales. Les machines adressables par mots -- une caracteristique
essentielle de l'aspect scientifique -- ont survecu plus longtemps;
peut-etre parce qu'IBM etait moins dominant sur ce marche.

(Question implementation, d'apres ce que j'ai lu, il y avait
souvent une base binaire soujacente au comportement
architectural decimal).


Au plus bas niveau... J'ai entendu parlé une fois d'une machine
expérimentale qui utilisait le base 3,


Russe, un prototype construit d'apres ce que j'ai compris. Elle etait
binaire mais les bits etaient groupes par deux et le quatrieme etat
servait a faire du controle d'erreur.

et d'après ce que j'ai entendu dire, une partie au moins des tout
premiers 8087 était implémenté en base 4 (mais ça ne paraissait pas
à l'exterieur -- c'était pour reduire la place nécessaire pour le
microcode, je crois).


S'il y a du base 4, je parie que c'est a nouveau en manipulant des
groupes de 2 bits.

Mais c'est vraiment les cas exceptionnels -- quand on parle du
décimal sur une machine, c'est en général du BCD, avec quatre bits
binaires.


Il y a eu aussi des representation biquinaires (2 bits a 1 choisis
parmi 5) et purement 1 bit choisi parmis 10.

Au moins pour le stockage et les registres, on a aussi utilise des
systemes ayant 10 etats physiques -- roues tournantes, tubes.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org




Avatar
Arnaud Meurgues
Jean-Marc Bourguet wrote:

Il y a eu aussi des representation bikinaires


Vi. C'est bientôt la saison... ;-)


--
Arnaud

Avatar
Jean-Marc Bourguet
Arnaud Meurgues writes:

Jean-Marc Bourguet wrote:

Il y a eu aussi des representation bikinaires


Vi. C'est bientôt la saison... ;-)


Je bosse a Sophia Antipolis ;-)

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org


Avatar
Arnaud Meurgues
Jean-Marc Bourguet wrote:

Il y a eu aussi des representation bikinaires
Vi. C'est bientôt la saison... ;-)

Je bosse a Sophia Antipolis ;-)



Ah. Alors c'est commencé depuis un moment.

Moi, ça commence maintenant.

--
Arnaud (à La Rochelle)



Avatar
Jean-Marc Bourguet
Arnaud Meurgues writes:

Jean-Marc Bourguet wrote:

Il y a eu aussi des representation bikinaires
Vi. C'est bientôt la saison... ;-)

Je bosse a Sophia Antipolis ;-)



Ah. Alors c'est commencé depuis un moment.


Il parait qu'il n'a pas fait tres beau. (Les gens du coin ont une
idee differente du beau temps qu'un Belge, meme present depuis neuf
ans :-)

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org




Avatar
Gabriel Dos Reis
Jean-Marc Bourguet writes:

| Arnaud Meurgues writes:
|
| > Jean-Marc Bourguet wrote:
| >
| > >>>Il y a eu aussi des representation bikinaires
| > >>Vi. C'est bientôt la saison... ;-)
| > > Je bosse a Sophia Antipolis ;-)
| >
| > Ah. Alors c'est commencé depuis un moment.
|
| Il parait qu'il n'a pas fait tres beau. (Les gens du coin ont une
| idee differente du beau temps qu'un Belge, meme present depuis neuf
| ans :-)

Ici, il fait très beau -- et c'est exceptionel me dit-on. Depuis plus
de 4 jours il fait entre 72 et 85. On n'a pas encore été
au-dessus de 105, pou run moi de mai.
Le semestre est fini depuis la semaine dernière, donc il n'y a plus de
confusions bikinaires...

-- Gaby
Avatar
Arnaud Meurgues
Gabriel Dos Reis wrote:
Jean-Marc Bourguet writes:
| Arnaud Meurgues writes:
| > Jean-Marc Bourguet wrote:
| > >>>Il y a eu aussi des representation bikinaires
| > >>Vi. C'est bientôt la saison... ;-)
| > > Je bosse a Sophia Antipolis ;-)
| > Ah. Alors c'est commencé depuis un moment.
| Il parait qu'il n'a pas fait tres beau. (Les gens du coin ont une
| idee differente du beau temps qu'un Belge, meme present depuis neuf
| ans :-)
Ici, il fait très beau -- et c'est exceptionel me dit-on. Depuis plus
de 4 jours il fait entre 72 et 85. On n'a pas encore été
au-dessus de 105, pou run moi de mai.


Ça fait quoi, en vrais degrés ? :-)

Le semestre est fini depuis la semaine dernière, donc il n'y a plus de
confusions bikinaires...


Ça te rend confus ?

--
Arnaud

1 2 3 4 5