Calculs du point de vue de la norme

Jean-Marc Bourguet wrote:

"kanze" <kanze@gabi-soft.fr> writes:

[...]

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.

C'était le but. Avant le 360, IBM (et tous les autres
constructeurs) avec des machines complètement différentes pour
les deux marchés -- et souvent, complètement différentes pour de
différents niveaux de performance à l'intérieur de chaque
marché. (Par complètement différentes, je veux dire : différente
architecture, avec un jeu d'instructions différent, une taille
de mots éventuellement différents, etc., etc.)

Une des innovations dans le cahier de charge du développement de
l'architecture 360, c'est qu'elle devait pouvoir tout faire, et
qu'elle soit implémentable aussi bien sur les machines bas de
gamme que celles les plus puissantes. Qu'une seule architecture
servira pour tout.

À mon avis, ils ont incroyablement bien fait leur travail. Même
aujourd'hui, selon les normes actuelles, l'architecture paraît
bien conçue. Beaucoup mieux que l'IA-32, évidemment, mais elle
supporte aussi bien la comparaison avec les architectures RISC
les plus modernes.

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.

Ou parce qu'on continuait à développer sur les anciennes
architectures. Le marché était moins lucratif, et donc,
justifiait moins d'investissements. Ou simplement parce qu'on
n'a pas reconnu l'intérêt de l'adressage octet tout de suite.
(Note bien aussi que sur une machine à 16 ou à 18 bits,
l'adressage mot permet à doubler la mémoire adressable. Ce qui a
un intérêt non negligeable sur des machines aussi petites.)

Aujourd'hui, autant que je sache, il ne reste plus qu'une seule
machine à adressage mot sur le marché : le Unisys 2200. (Qui
est, en passant, une machine de gestion -- son fort, c'est la
gestion des bases de données énormes.)

En ce qui concerne le décimal -- l'IBM 390 d'aujourd'hui a
encore des instructions en hardware pour les quatres opérations
BCD (et pour la conversion entre les BCD et les entiers). Et
l'IA-32 a des instructions soi-disant pour facilité
l'arthimétique décimale -- pour l'addition et la soustraction,
elles apportent réelement, mais pour la multiplication et la
division, je l'ai trouvé sans intérêt. Aussi, le processeur
flottant permet la lecture et l'écriture des BCD. On ne peut
donc pas dire que le décimal est complètement mort.

(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.

C'en est une autre, alors. Celle dont j'ai entendu parler,
c'était en France. Et c'était réelement du base trois. Mais je
ne sais pas si elle a jamais été réalisée -- je crois que
c'était une conception théorique, sur papier.

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.

Au contraire. Le problème, c'était de gagner de la place dans le
ROM du microcode. La solution, c'était bien un discriminateur à
quatre niveaux de tension, avec des ponts plus ou moins ajuster
pour donner le bon niveau selon les valeurs binaires voulues.

De prèsqu'on m'a racconté, cette version n'est jamais arrivée à
la production en série. Elle a servi dans les prototypes, livrés
aux clients privilégés (dont mon employeur à l'époque), où on a
constaté qu'elle était trop sensible aux variations de
temparature et de tension d'alimentation.

Je dois ajouter que c'est un employé d'Intel qui me l'a
racconté. Tout ce que je sais de mes propres expériences, c'est
que c'est bien vrai que dans les pré-séries des 8087, la valeur
de pi (et pratiquement tous les autres résultats) dépendait de
la temparature du chip et sa tension d'alimentation. Et que le
problème était résolu dans la première livraisons en séries.
L'histoire des quatre niveaux expliquerait bien les symptomes,
et la personne qui me l'a racconté était bien positionné pour
savoir. Il peut y avoir cependant d'autres explications, et la
personne aurait pû simplement racconter des blagues. Mais c'est
plausible.

--
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

Jean-Marc Bourguet wrote:

Sylvain <noSpam@mail.net> writes:

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>.

Pas besoin de constuirer beaucoup, c'est le cas avec mon jeu de
données par défaut (construire en semant le générateur aléatoire
avec 1). Et sur Sparc, et sur PC.

Ce qui est intéressant, c'est que c'est moins précis que sumUp
sur PC. La fonction sumUp est assez simple pour que g++ réussi à
faire tout le calcul dans des régistres à précision étendu --
c'est donc 64 bits de mantisse, à la place de 24. Ce qui suffit,
au moins dans le cas d'une million d'éléments seulement, à
éliminer l'erreur. (Et à invalider le benchmark -- au moins en
ces efforts de démonter la différence de précision entre les
différents algorithmes.)

(Ce qui m'étonne aussi, c'est qu'il n'y a pas d'erreurs
constatables avec sumBinary sur les valeurs triées.)

--
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

"kanze" <kanze@gabi-soft.fr> writes:

C'en est une autre, alors. Celle dont j'ai entendu parler,
c'était en France. Et c'était réelement du base trois. Mais je
ne sais pas si elle a jamais été réalisée -- je crois que
c'était une conception théorique, sur papier.

De celle-la je n'avais pas entendu parler.

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.

Au contraire. Le problème, c'était de gagner de la place dans le ROM
du microcode. La solution, c'était bien un discriminateur à quatre
niveaux de tension, avec des ponts plus ou moins ajuster pour donner
le bon niveau selon les valeurs binaires voulues.

Ca me semblait tellement risque que je n'ai pas pense qu'ils aient
quand meme essaye. Je suis rassure de voir que mon evaluation du
risque n'etait pas si sous-estimee que cela.

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

"kanze" <kanze@gabi-soft.fr> writes:

Ce qui est intéressant, c'est que c'est moins précis que sumUp
sur PC. La fonction sumUp est assez simple pour que g++ réussi à
faire tout le calcul dans des régistres à précision étendu --

bug connu de gcc. Mais je t'ai repondu la-dessus sur csc++.

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

Jean-Marc Bourguet wrote on 17/05/2006 15:19:

Sylvain <noSpam@mail.net> 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)?

pour cet objectif, elles sont très bien... si utilisées correctement [1]

je me plaçais dans un cadre de traitement numérique et commentais le
main() de James qui ne contient que des SumXXX<float>; là je maintiens
que un SumUp<double> est suffisant.

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.

tu ne comprends pas quoi ? que le nombre de chiffres significatifs est
limité ? que (float)(500000. + 0.512345) vaut 500000. et non 500000.512345 ?

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).

le problème est que pour la valeur 0.512345 lorsqu'elle est ajouté à
500000. c'est même son UFP qui se volatilise avec les SumUp/Down;
SumPriority réalise un calcul avec une précision de double via 3 floats
et 3 opérations, il conserve donc un résultat où l'ULP du resultat-float
est correct.

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

Meme principe que sumBinary, mais deux niveaux seulement.

de manière un peu détourné mais en effet sumBin revient à faire 500000
sommes entre arguments de même magnitude puis 250000 sommes entre, etc.

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>.

c'est même très facile !!

comme il est facile de faire converger ou diverger SumUp resp. SumDown
(il suffit par exemple de trier le tableau avant la somme).

une méthode plus générique, ne dépendant pas notamment de la qualité du
randomizer et de l'ordonnencement des valeurs à sommer mais traitant de
valeurs à écart type faible de:

a) calculer la moyenne (ici 0.5)
b) accumuler des valeurs tant que les résultats ne dépasse pas 100 fois
cette moyenne (pour ne perdre que 2 chiffres significatifs entre ce
résultat et un élément à sommer)
c) stocker cette somme dans un vector intermédiaire
d) boucler pour épuiser les valeurs.

e) considérer les éléments du vecteur de résultats intermédiaires comme
le nouvel array d'input et bouclé en 1.

on aura ainsi un sumBinaryTierce dont le niveau dépend de la distribution.

Sylvain.

kanze wrote on 17/05/2006 14:10:

On peut le dire, vue qu'il fait que j'ai des résultats
différents selon le niveau d'optimisation, sans changer ni le
compilateur ni le CPU. (Et sans avoir un comportement indéfini
ni non-spécifié.)

on est d'accord pour dire qu'un code différent (y compris source
identique, binaire optimisé différemment) peux donner des résultats
différents.

c'est pourquoi je n'autorise aucune optimisation sur des routines
numériques flottantes - le code à exécuter doit être le mien et non
l'invention du compilo (et ça aide à la portabilité/constance).

Tu trouves que ce n'est pas étonnant que je n'ai pas obtenu le
même résultat ? J'avais l'impression que tu disais que les
résultats étaient indentiques sur un même processeur. C'est bien
un contre-exemple. (Mais peut-être j'ai mal compris ce que tu
voulais dire.)

je le supposais depuis le début: pour un code entièrement controlé, pas
pour un code où le compilo change la précision des intermédiaires et
l'ordre des évaluations.

Alors, de quoi sers-tu pour comparer, si tu n'utilises ni les
tests d'équalité, ni les tests d'ordonnencement ?

éventuellement ces opérateurs non appliqués au types primitifs mais
surchargés par une classe ayant calculé l'erreur (la précision c'est du
même) de l'insatnce à chaque opération l'impliquant.

Bien, je supposais que tu disais quelque chose d'utile. Qu'un
résultat soit connu à une précision donnée n'a d'utilité que si
on connaît cette précision. Et comme j'ai montré, cette
précision varie selon le contexte.

(excuses-moi d'avoir été obligé de détailler de manière kilométriquement
ennuiyeuse!)

qui a dit qu'il était interdit de calculer justement cette précision?

Pas de problème -- elle ne sont pas de moi. J'étais simplement
curieux aux différences réeles de précision et de vitesse. (De
prèsque j'ai compris d'après les discussions, le sumCompensated
est plus ou moins la solution standard parmi les spécialistes
dans la numérique.

et en électronique (code embarqué) c'est _la_ façon de faire lorsqu'il
n'existe pas de type plus étendu que les opérandes.

Je pourrais ajouter qu'ici on a un problème où la précision
supplémentaire des valeurs intermédiaire sur l'Intel a un
avantage. Sur le PC Linux, j'ai exactement les mêmes résultats
dans les tests de précision, quelque soit l'algorithme utilisé.

je ne te crois pas ! ;)

plus clairement ils le sont parce que tes appels SumXXX<float> sont
strictement équivalents à des SumXXX<double> parce que tu as laissé le
compilo "optimiser" (faire ce qu'il voulait) et qu'il ne se gène pas de
virer ta variable accumulateur qui ne lui sert à rien (préférant un
registre long du FPU).

si tu fais un run sans aucun optim. tu auras des différences.

Pas vraiement. D'abord, les valeurs flottantes sont, par défaut,
toutes dans l'intervalle 0-1,0. Alors, je sais que je n'aurais
pas de débordement de valeur.

j'ai dit "débordement relatif" - lorsque l'on somme
500 000.
+ .512345
et que le résultat ne peut avoir que 6 chiffres significatifs, il a y
débordement qui donne (visiblement)
500 001.
et un peu mieux en interne (en tout cas sur Intel comme tu l'as déjà
indiqué).

Deuxièmement, vouloir savoir le moyen d'un grand
nombre valeurs me semble un problème raisonable
-- une réponse du genre on ne sait pas le faire
avec un ordinateur ne me semble pas acceptable.

qui oserait faire ce type de réponse ?
heureusement que l'on sait faire!

[...] (Autant que je me rappelle, Jean-Marc a
posté l'algorithme sumPriority comme un exemple d'un algorithme
« naïf » dans l'autre sens -- c'est la solution trivialement
évident pour réduire l'erreur au maximum, mais à quel coût !)

il est couteux et "compréhensible" (on "comprend" que c'est la façon de
faire, la façon dont est faite l'erreur et dont il convient de la corriger).

(Évidemment, dans n'importe quelle utilisation réele,
j'utiliserais double pour l'accumulateur de la somme, et non
float. Ici, le but était en partie de voir le comportement des
algorithmes par rapport aux pertes de précision -- et on voit
plus clairement quand les pertes de précision sont plus
grandes.)

arrêtes d'optimiser, tu les verra encore mieux ;)

l'autre point corrollaire pertinent est la précision
intermédiaire que tu évoquais; puisque les calculs sont en
boucle le résultat intermédiaire (qui contient qlq chose comme
500000.512345 en fin de boucle) est tronqué à un float (6
chiffres significatifs, donc 500000.) et donc fausse
complètement le résultat.

Il doit l'être, selon la norme C++. D'après les résultats, j'ai
l'impression qu'il ne l'est pas avec le compilateur g++ sur
PC/Linux.

je parie également mon dessert qu'il ne l'est pas du tout.

Coût et danger rélatifs. sumBinary est nettement plus rapide que
sumPriority (un ordre de magnitude, quand même), et

je n'ai pas essayé sunPriority (compilo trop archaïque).

Je sais. J'ai utilisé float exprès, vue que le but était de
comparer le comportement des *algorithmes*, par rapport aux
arondi. J'ai fait en sort de maximiser ce que je voulais
mesurer.

alors utilise _vraiment_ des floats (pas les registres du FPU).

comme tu disais,il est important de savoir ce que l'on fait --
et ici il faut comprendre que garder 6 chiffres significatifs
entre 2 opérandes ayant 6 magnitudes d'écart impose de traiter
ces opérations avec 12 chiffres significatifs.

(7 chiffres significatifs, en fait).

non je ne pense pas que 7 suffisent.

nota: j'ai indiqué partout "6" par simplicité, en fait cela
correspondrait à une représentation décimale des nombres ce qui n'est
pas le cas, ça sera 6 ou 7, qu'importe.

Sauf sumUp et sumDown, je crois que je n'ai jamais de cas où il
y a six magnitudes d'écart.

bien sur que si; dans sumCompensated (pour 0 << i < size) result
contient qlq chose k00000.0 (k in 1..5) et error une valeur entre 0.0 et 1.0

L'idée derrière sumPriority et sumBinary, en fait, c'est
que les magnitudes soient toujours à peu près identiques

oui.

sumPriority le garantit (à un prix exhorbitant),

au moins exhorbitant ! ;)

et sumBinary joue sur la statistique -- c'est
d'ailleurs pourquoi dans mes tests de précision j'ai fait des
tests avec le tableau trié ; c'est le cas le plus défavorable
pour sumBinary (en ce qui concerne la précision).

yep, il aurait fallu traiter les extrèmes ensemble dans ce cas, en gros:

template< typename T >
T sumBinary( float const* array, size_t size )
{
return array[0] + array[size-1] +
(size == 2) ? 0.0 : sumBinary<T>(array + 1, size - 2);
}

il vient que (array étant un float[]):
double result = 0.0;
for (size_t i = 0; i < size; ++i)
result += array[i];

est bien l'écriture la plus compacte, simple et intuitive qui
donne le bon résultat.

Il s'avère qu'on ne peut pas garantir non plus qu'elle donne le
bon résultat. Il y a toujours des erreurs d'arrondi. Moins
qu'avec float, mais il y en a quand même.

"bon résultat" est un abus - disons le meilleur float-résultat possible.

Dans mes tests, j'utilisais les tableaux avec une taille d'une
million d'éléments. Des tableaux assez petits, en somme, mais
j'ai une vieille machine, pas très rapide, qui sert aussi à
d'autres choses, et je n'ai pas voulu la surcharger trop pendant
trop longtemps. J'ai donc modifié mes tests initiaux pour que
les effets de l'arrondi se fassent sentir sur des tableaux plus
petits. (Il faut dire surtout que j'ai assez peu de mémoire. Et
quand le test se met à pager, ça ralentit tout, beaucoup.)

le tableau ne fait que 4 Mo !?! ... ah oui swapper la récursivité :)

Et qu'est-ce que tu penses que sumBinary fait ?

il utilise de la même façon des calculs partiels - mais via une
récursivité, je voulais une solution sans récur.

PC, Linux, g++ :

Floating point tests:

non <double> point tests !

Sylvain.

Sylvain wrote:

kanze wrote on 17/05/2006 14:10:

On peut le dire, vue qu'il fait que j'ai des résultats
différents selon le niveau d'optimisation, sans changer ni
le compilateur ni le CPU. (Et sans avoir un comportement
indéfini ni non-spécifié.)

on est d'accord pour dire qu'un code différent (y compris
source identique, binaire optimisé différemment) peux donner
des résultats différents.

L'optimisation ne fait pas partie du code. La question,
justement, c'est jusqu'à quel point les choses peuvent varier.
(D'après ce que je comprends de la norme, ou au moins, ce que
j'ai toujours cru en être l'intention des auteurs, le
comportement de g++ dans ce cas-ci est une erreur.)

c'est pourquoi je n'autorise aucune optimisation sur des
routines numériques flottantes - le code à exécuter doit être
le mien et non l'invention du compilo (et ça aide à la
portabilité/constance).

Donc, tu écris en assembleur. Sinon, le code qui s'exécute est
toujours « l'invention du compilateur ».

Une partie de cette discussion tourne autour de ce qui est
garantie par le langage, et ce qui ne l'est pas. Et tu ne peux
pas s'attendre à ce qu'un compilateur se conforme à ce qui n'est
pas exigé par le langage. Dans le cas des processeurs Intel, par
exemple, même sans l'optimisation, un compilateur va garder des
résultats intermédiaire d'une expression complexe dans des
régistres flottant, donc en précision étendue. Sauf, évidemment,
s'il lui manque des régistres. Ce qui fait qu'éventuellement, la
même sous-expression peut avoir des valeurs différentes selon
l'expression dans laquelle elle apparaît.

Tu trouves que ce n'est pas étonnant que je n'ai pas obtenu
le même résultat ? J'avais l'impression que tu disais que
les résultats étaient indentiques sur un même processeur.
C'est bien un contre-exemple. (Mais peut-être j'ai mal
compris ce que tu voulais dire.)

je le supposais depuis le début: pour un code entièrement
controlé, pas pour un code où le compilo change la précision
des intermédiaires et l'ordre des évaluations.

Donc, un code en assembleur, et non en C++. Le langage C++
permet exprès au compilateur d'utiliser les intermédiaires d'une
précision plus grande, et ne définit pas d'ordre d'évaluation.

Alors, de quoi sers-tu pour comparer, si tu n'utilises ni
les tests d'équalité, ni les tests d'ordonnencement ?

éventuellement ces opérateurs non appliqués au types primitifs
mais surchargés par une classe ayant calculé l'erreur (la
précision c'est du même) de l'insatnce à chaque opération
l'impliquant.

C'est à dire que tu redéfinis == pour signifier « à peu près » ?
Pour quelle valeur d'« à peu près » ? Et comment tu gères le
problème que tu n'as plus de rélation d'équalité -- que ton ==
n'est pas transistive ?

Et en fin de compte, comment est-ce que tu implémentes ces
opérateurs, sans se servir des opérateurs de comparaison du
langage ?

Je pourrais ajouter qu'ici on a un problème où la précision
supplémentaire des valeurs intermédiaire sur l'Intel a un
avantage. Sur le PC Linux, j'ai exactement les mêmes résultats
dans les tests de précision, quelque soit l'algorithme utilisé.

je ne te crois pas ! ;)

Essaie. J'ai donné un URL d'où tu peux télécharger le code.
N'importe qui (qui a accès à un PC, évidemment) peut dupliquer
exactement ce que j'ai fait -- Linux et g++ sont gratuit ; ce
n'est donc que le PC qui pourrait poser de problème.

plus clairement ils le sont parce que tes appels SumXXX<float>
sont strictement équivalents à des SumXXX<double> parce que tu
as laissé le compilo "optimiser" (faire ce qu'il voulait) et
qu'il ne se gène pas de virer ta variable accumulateur qui ne
lui sert à rien (préférant un registre long du FPU).

D'abord, il sont tous les deux plus ou moins l'équivalent de
sumUp< long double >. (Et ça ne vaut que pour sumUp et sumDown.
Les autres sont assez compliqués pour que le compilateur ne peut
pas garder toutes les valeurs dans des régistres.)

Je crois, en effet, qu'ici il s'agit d'une erreur de
compilateur. Mais qu'est-ce qui te dit que la même erreur ne se
présente pas dans la version non-optimisée ? Les auteurs de g++
ont apparamment décidé que la liberté donnée par le langage C++
de maintenir des résultats en précision étendue s'étend même au
cas où le résultat est stocké dans une variable nommée. En en
rélisant la norme, je constate que ce n'est pas aussi clair
qu'on pourrait souhaiter qu'ils ont tort.

À la fin, tu as deux choix. Tu fais confiance à ton compilateur
de respecter la norme, et tu écris du code qui marche selon la
norme, ou tu écris en assembleur.

si tu fais un run sans aucun optim. tu auras des différences.

Et qui fait le calcul numérique sans optimisation. S'il y a un
domaine où la performance prime, c'est bien le calcul numérique.

Pas vraiement. D'abord, les valeurs flottantes sont, par
défaut, toutes dans l'intervalle 0-1,0. Alors, je sais que
je n'aurais pas de débordement de valeur.

j'ai dit "débordement relatif" - lorsque l'on somme
500 000.
+ .512345
et que le résultat ne peut avoir que 6 chiffres significatifs, il a y
débordement qui donne (visiblement)
500 001.
et un peu mieux en interne (en tout cas sur Intel comme tu l'as déjà
indiqué).

Ce n'est pas un débordement, mais une perte de précision. La
fonction sumBinary représente un effort naïf pour le limiter.
sumPriority garantit de restreindre l'effet au maximum, à un
coût exhorbitant en temps d'exécution, et sumCompensated corrige
au fur et à mesure (si je l'ai bien compris).

[...] (Autant que je me rappelle, Jean-Marc a
posté l'algorithme sumPriority comme un exemple d'un algorithme
« naïf » dans l'autre sens -- c'est la solution trivialement
évident pour réduire l'erreur au maximum, mais à quel coût !)

il est couteux et "compréhensible" (on "comprend" que c'est la
façon de faire, la façon dont est faite l'erreur et dont il
convient de la corriger).

Tout à fait.

(Évidemment, dans n'importe quelle utilisation réele,
j'utiliserais double pour l'accumulateur de la somme, et non
float. Ici, le but était en partie de voir le comportement
des algorithmes par rapport aux pertes de précision -- et on
voit plus clairement quand les pertes de précision sont plus
grandes.)

arrêtes d'optimiser, tu les verra encore mieux ;)

L'optimisation ne fait aucune différence avec Sun CC sur Sparc.
Mais quand on manipule des tableaux avec des millions de
valeurs, la performance cesse d'être une question sécondaire, et
l'utilisation de l'optimisateur est de rigueur. Ce n'est pas un
hazard que la plupart des récherches sur l'optimisation ont eu
lieu sur Fortran.

[...]>

comme tu disais,il est important de savoir ce que l'on fait --
et ici il faut comprendre que garder 6 chiffres significatifs
entre 2 opérandes ayant 6 magnitudes d'écart impose de traiter
ces opérations avec 12 chiffres significatifs.

(7 chiffres significatifs, en fait).

non je ne pense pas que 7 suffisent.

Je voulais dire que les float IEEE ont 7 chiffres significatifs.

Mais ce n'était qu'une remarque parenthètique, parce que ça ne
change rien au problème. Grosso modo, si je comprends ce que tu
veux dire, c'est que si j'ajoute deux nombres de 6 chiffres, il
faut que j'utilise l'arithmétique à 12 chiffres, et que je garde
le résultat sur 12 chiffres (minimum, évidemment). Que la
précision nécessaire est la somme des précisions en entrée. Ce
qui pose un petit problème : la précision nécessaire augmente
alors à chaque itération. Et j'ai des millions d'itérations.

[...]

et sumBinary joue sur la statistique -- c'est d'ailleurs
pourquoi dans mes tests de précision j'ai fait des tests
avec le tableau trié ; c'est le cas le plus défavorable pour
sumBinary (en ce qui concerne la précision).

yep, il aurait fallu traiter les extrèmes ensemble dans ce cas, en gros:

template< typename T >
T sumBinary( float const* array, size_t size )
{
return array[0] + array[size-1] +
(size == 2) ? 0.0 : sumBinary<T>(array + 1, size - 2);
}

Ce qui maximisera l'erreur sur la première addition. Ce n'est
pas dit que ça donnera un meilleur résultat.

Mais qu'importe. Pourquoi chercher à améliorer sumBinary, quand
sumCompensated donne déjà un résultat garanti correct dans des
bornes très étroit (et donc meilleur que celui de sumBinary), et
est plus rapide.

Dans mes tests, j'utilisais les tableaux avec une taille
d'une million d'éléments. Des tableaux assez petits, en
somme, mais j'ai une vieille machine, pas très rapide, qui
sert aussi à d'autres choses, et je n'ai pas voulu la
surcharger trop pendant trop longtemps. J'ai donc modifié
mes tests initiaux pour que les effets de l'arrondi se
fassent sentir sur des tableaux plus petits. (Il faut dire
surtout que j'ai assez peu de mémoire. Et quand le test se
met à pager, ça ralentit tout, beaucoup.)

le tableau ne fait que 4 Mo !?! ... ah oui swapper la
récursivité :)

Je ne comprends pas la rémarque. J'aurais voulu faire des essais
avec des tableaux de 100 millions d'entrées. Seulement, la
machine sur laquelle je travaille d'habitude n'a que 256 Mo de
mémoire réele (et il y a aussi d'autres choses qui tourne
dessus). Et une fois le tableau ne tient plus en mémoire vive,
les temps d'exécutions deviennent trop, même pour les
algorithmes les plus simples. (Je n'aimerais pas penser à
l'effet sur sumPriority, dont la localité de référence est
particulièrement mauvaise.)

--
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

Sylvain wrote:

[...]

une méthode plus générique, ne dépendant pas notamment de la
qualité du randomizer et de l'ordonnencement des valeurs à
sommer mais traitant de valeurs à écart type faible de:

a) calculer la moyenne (ici 0.5)
b) accumuler des valeurs tant que les résultats ne dépasse pas 100 fo is
cette moyenne (pour ne perdre que 2 chiffres significatifs entre ce
résultat et un élément à sommer)
c) stocker cette somme dans un vector intermédiaire
d) boucler pour épuiser les valeurs.

e) considérer les éléments du vecteur de résultats intermédiair es comme
le nouvel array d'input et bouclé en 1.

on aura ainsi un sumBinaryTierce dont le niveau dépend de la
distribution.

On aura ainsi un algorithme qui donne toujours moins de
précision que l'algorithme « standard » (sumCompensated), tout
en prenant beaucoup plus de temps.

--
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

kanze wrote:

Mais ce n'était qu'une remarque parenthètique, parce que ça ne
change rien au problème. Grosso modo, si je comprends ce que tu
veux dire, c'est que si j'ajoute deux nombres de 6 chiffres, il
faut que j'utilise l'arithmétique à 12 chiffres, et que je garde
le résultat sur 12 chiffres (minimum, évidemment). Que la
précision nécessaire est la somme des précisions en entrée.

Là, je ne suis plus certain de suivre. La précision d'un flottant, c'est
la précision de sa mantisse, il me semble (qui correspond au nombre de
chiffres significatifs).
Mais si l'on additionne deux flottants avec un même nombre de chiffres
significatifs, mais des exposants très éloignés, on fait bien plus que
doubler le nombre de chiffres significatifs nécessaires pour conserver
la précision voulue.

Du coup, je ne comprends pas pourquoi il faudrait particulièrement 12
chiffres significatifs pour additionner deux nombres ayant 6 chiffres
significatifs.

--
Arnaud

Arnaud Meurgues wrote on 19/05/2006 11:27:

Du coup, je ne comprends pas pourquoi il faudrait particulièrement 12
chiffres significatifs pour additionner deux nombres ayant 6 chiffres
significatifs.

excès de "normalisme" ? ;) - le point n'étant pas ce que garantit la

norme, tel compilo ou que sais-je.

simplement: soit une somme de 10^6 nombres compris dans [0.0 .. 1.0[

j'ai peur de me voir réprocher des contradictions (formelles, non
pratiques) si j'ajoute que tout cela est invalide pour une somme d'un
milliard de nombres...

Sylvain.