Priorité et associativité des opérateurs

On 09/09/2010 11:24 AM, Wykaaa wrote:

Lucas Levrel a écrit :

Le 9 septembre 2010, Alexandre Bacquart a écrit :

Par contre, je crois que des formulation comme (a-b)-c ou a-(b+c) sont
effectivement auto-documentées, rajoutant explicitement une information
C'est surtout vrai lorsque, comme dans le premier cas, elles sont
syntaxiquement inutiles, donc n'ont de portée sémantique qu'à
destination de celui qui lit, comme n'importe quel commentaire.

Je partage ton avis sur le premier cas, mais pour le deuxième, c'est
le changement d'expression qui est susceptible de me gêner dans
certains contextes. J'ai bien dit "susceptible".

Il me semble que le point de vue de JKB est : a-b-c montre que le
programmeur ne s'est pas posé la question des cas limites,
contrairement à a-(b+c) ou (a-b)-c. Les deux dernières sont donc
préférables à la première, mais (et il me semble que c'est ce sur quoi
tu insistes) un mainteneur ne devrait pas remplacer a-b-c par a-(b+c)
*uniquement* pour améliorer la lisibilité, il ne peut pas se passer de
scruter les cas limites.

Oui, le résultat est le même puisqu'on est dans R (passons le fait
que strictement, l'équivalence est fausse et qu'on est pas totalement
dans R, inutile d'alourdir le débat ici avec des UB de magnitudes ou
de débordements), mais à mes yeux, l'expression est *différente*
avant d'être *formelle et préférable*.

Dans R, a-b-c=a-(b+c) et quelqu'un qui utilise couramment les maths
n'interprétera pas différemment les deux formes.

Il ne faut pas confondre l'ensemble R des réels en mathématique et les
nombres flottants en programmation. Les deux domaines n'ont pas
grand-chose en commun. La première chose que nous a dite le prof
d'informatique, à la première heure de cours (c'était en 1970 pour ce
qui me concerne) c'est : "vous pouvez demander beaucoup de choses à un
ordinateur mais pas de stocker racine carrée de 2". Il n'y a pas de
nombres irrationnels en informatique !

Quand on écrit a-b-c, normalement, puisque l'opération est associative à
gauche, les calculs se feront comme si on avait écrit : (a-b)-c
(soustraction de b à a puis soustraction de c au résultat.
Si on écrit a-(b+c), ceci n'a rien à voir avec le calcul précédent car
l'ordre de calcul est le suivant :
addition de b+c puis soustraction de ce résultat à a.
L'addition b+c peut engendrer un overflow qui ne peut se produire avec
l'écriture précédente !
Du point de vue de l'exécution, les deux écritures sont très
différentes. D'ailleurs, un optimiseur est parfaitement en droit, pour
l'expression a-b-c, de calculer (a-c)-b mais il ne devrait pas se
permettre de calculer cette expression de la façon a-(b+c).
Cependant, et les gens du calcul numérique le savent bien, si l'on veut
que les calculs soient exécutés exactement comme on les a écrits, il faut :
1) décomposer toute expression au maximum
2) débrayer toute option d'optimisation à la compilation

La différence cruciale apparaît en analyse numérique avec les cas
limites, qui ne sont absolument pas des /undefined behaviours/ soit
dit en passant !

Et je sais tout cela depuis longtemps. Je suis précisément, en ce
moment, dans ce bain là, notamment en ce qui concerne les flottants
car j'ai justement besoin de représenter des quantités astronomiques
(de l'ordre de l'année-lumière par rapport au centimètre) et étant
donné mes pré-requis, je vais devoir tricher (les doubles ne
résolvent pas le problème).

Et les long double ? Sur mon système LDBL_DIG=

Les long double ne sont pas portables en C.

Je ne suis que peu concerné par cette portabilité là. Mais quand bien
même, long double ne me convient pas plus que double.

Il existe des librairies qui savent effectuer les calculs en précision
arbitraire comme MPFR
(http://interstices.info/jcms/c_9345/mpfr-vers-un-calcul-flottant-correct?portal=j_97&printView=true).

C'est hélas difficilement envisageable car l'un de mes pré-requis est
OpenGL. Si ce n'est pas moi qui me vautre, ce sera lui. De plus, j'ai
certaines exigences de performances (milliards d'opérations par seconde
à un rythme soutenu). Le scénario idéal serait bien-sûr que je puisse
appliquer une précision arbitraire dans toute la chaîne de calcul, mais
ça serait trop simple :)


--
Alex

On 09/08/2010 02:49 AM, Alexandre Bacquart wrote:

je fais souvent :

(a == b) && (c == d)
plutôt que :
a == b && c == d

(a & b) || (c & d) || (e & f)
plutôt que :
a & b || c & d || e & f

+1, j'aime bien ne pas me prendre la tête.

--
Et pendant ce temps-là, dans le septembre éternel...

Samuel DEVULDER a écrit :

Le 09/09/2010 14:02, Wykaaa a écrit :

Tout dépend de l'arithmétique utilisée. Avec iRRAM, aucun problème
pour manipuler les irrationnels, qui sont représentés *exactement*
par des arbres de calcul.

Tiens je ne connais pas cette bibliothèque. Dans le peu de connaissance
que j'ai des outils de manips formelles de nombres le fait de détecter
qu'une formule vaut exactement zéro a toujours été problématique.

Sais tu comment se passe la détection du zéro dans iRRAM? Est-ce qu'elle
peut effectivement tester la nullité de n'importe quel arbre de calcul
ou est-ce qu'elle ne s'applique que sur les classes de nombres/formules
où l'on sait décider le zero?

sam.

Fais attention dans tes réponses car tu m'as attribué un message écrit
par Vincent Lefevre.
Moi non plus je ne connaissais pas iRRAM...

Pierre Maurette écrivit :

JKB, le 09/09/2010 a écrit :

[...]

Lorsque tu écris a - b - c, tu ne sauras _jamais_ si le type qui a
codé ça l'a fait en toute connaissance de cause alors que si tu
avais (a - b) - c ou a - (b + c), tu n'aurais plus aucun doute.

Pas d'accord. Si dans tout le code, je ne trouve *jamais* a - b - c mais
plutôt systématiquement (a - b) - c et plus généralement des parenthèses
partout, je ne peux _plus_ déduire qu'il y eut une analyse qui justifie
l'utilisation de (a-b)-c plutôt que de a-(b+c) ; j'aurais plutôt
tendance à considérer que le programmeur est du genre ceinture-et-bretelles.

En fait, c'est le côté exceptionnel d'une formulation qui lui donne un
supplément de sens ; a contrario, si c'est systématique il n'y a plus de
supplément : rien ne vient gratuitement, et un programmeur peut
difficilement fait croire à tort qu'il a bossé, simplement en rajoutant
systématiquement des parenthèses partout.

Et si /le type/ code (a - b - c), vous en déduisez que logiquement:
- /le type/ a codé /en toute connaissance de cause/.
- /le type/ est un peu tordu, ou simplement mutin.

:-))) mais je décanterai pour le deuxième, voire pour
- il y a une faute de frappe, méfiance
- le code a déjà été modifié X fois, et il reste des scories ;
il serait peut-être temps de regarder de plus haut => revue de code


Antoine

Wykaaa écrivit :

Samuel DEVULDER a écrit :

Le 09/09/2010 11:24, Wykaaa a écrit :

"ordinateur mais pas de stocker racine carrée de 2". Il n'y a pas de
nombres irrationnels en informatique !

<mode mutin=on>Peut de temps après sortait MuMath sur Apple2 et montrait:
1- qu'il avait tord dans les faits: les ordis savent parfaitement
stocker et manipuler sqrt(2) très exactement.
</mode>

Sachant que l'assembleur du 6502 ne possédait même pas la
multiplication, je n'ose imaginer les temps de calcul pour des calculs
numériques un peu tordus...

Est-ce un vrai souci pour les calculs formels ?

Surtout que l'absence de multiplication signifiait aussi que les autres
opérations comme les indexations ou la page 0 étaient plus rapides...


Antoine

Le 09/09/2010 16:39, Wykaaa a écrit :

Samuel DEVULDER a écrit :

Le 09/09/2010 14:02, Wykaaa a écrit :

Tout dépend de l'arithmétique utilisée. Avec iRRAM, aucun problème
pour manipuler les irrationnels, qui sont représentés *exactement*
par des arbres de calcul.

Tiens je ne connais pas cette bibliothèque. Dans le peu de
connaissance que j'ai des outils de manips formelles de nombres le
fait de détecter qu'une formule vaut exactement zéro a toujours été
problématique.

Sais tu comment se passe la détection du zéro dans iRRAM? Est-ce
qu'elle peut effectivement tester la nullité de n'importe quel arbre
de calcul ou est-ce qu'elle ne s'applique que sur les classes de
nombres/formules où l'on sait décider le zero?

sam.

Fais attention dans tes réponses car tu m'as attribué un message écrit
par Vincent Lefevre.
Moi non plus je ne connaissais pas iRRAM...

Ah oui pardon désolé.

En attendant que Vicent confirme ou infirme.. j'ai rapidement lu le PS
(arg.. de nos jour c'est PDF le standard) de la lib. Si j'ai pas tout
compris de travers, en fait il n'y a pas de test à ZERO et on ne peut
décider de l'égalité de deux REELS. Il n'y a que des tests de proximité
entre 2 réels avec tolérance. Idem pour les signes.

Par contre la bibliothèque introduit la notion de limite qui permet de
faire abstraction dans une certaine mesure de la précision. En fait la
limite est une espèce d'itérée de fonctions jusqu'à atteindre la
précision requise. Par exemple ils définissent sqrt1 à la précision
2^-n, et définisse sqrt (le vrai) comment étant la limite de la fonction
sqrt1 lorsque n->OO.

Cette bibliothèque est marante car en fait si en cours de route il se
rend compte qu'il ne peut pas avoir la bonne précision pour décider un
test, elle fait alors un longjmp en début de prog et le rejoue avec une
précision augmentée. Je trouve l'idée rigolote (il fallait oser), mais
ca doit conduire à des perfs désastreuses et des effets spéciaux sur les
IO. Du coup on a pas le droit d'utiliser les IO ni le malloc ni pleins
d'autres trucs avec cette bibliothèque. Son usage en est donc forcément
réduit.

Là où j'ai un doute sur ma lecture c'est que Vincent a parlé de l'arbre
de calcul.. Or en survolant la doc, j'ai plutôt eu l'impression que
l'arbre de calcul c'est l'exécutable lui même et que iRRAM ne fait que
maintenir les calculs à la bonne précision avec le longjmp magique qui
fait refaire toute l'exécution du programme (donc tout le calcul) avec
une précisions augmentée en cas de soucis. Là ou ca colle pas avec
l'idée de l'arbre de calcul que j'imaginais symbolique, c'est que s'il
était maintenu dans les objets REELS, il aurait suffit de tout
ré-évaluer avec une meilleurs précision sans faire rejouer le prog
depuis le début.

Peut-être qu'en fait c'est lié au fait que le rejeu ne serait pas
suffisant car avec une meilleure précision l'arbre de calcul doit
probablement devenir faux. Par exemple si on double le nombre de digits,
les méthodes quadratiques de calcul utilisée par la bibliothèque telle
que sqrt() ou l'inversion de nombre devront faire une passe de plus, et
donc l'arbre augmenter d'un niveau, invalidant l'arbre précédent. Ouais
ca doit être un truc dans ce goût là.

sam.

Dans l'article <4c88d1a6$0$5417$ba4acef3@reader.news.orange.fr>,
Wykaaa <wykaaa@yahoo.fr> écrit:

Il ne faut pas oublier qu'on souhaite, en général, que les langages de
programmation courants soient de type 2 de Chomsky (langages
context-free analysables par des automates à pile). Si on introduit une
précédence différente pour le - unaire utilisé sur une expression
"puissance", je ne suis pas certain qu'on reste "context-free" et les
langages de type 1 (contextuels) ne sont analysables que par des AMLB
(automates à mémoire linéairement bornée) ce qui devient assez
impraticable pour des programmes "réalistes".

Je ne parle pas de mettre une précédence différente, mais d'avoir
systématiquement la même précédence que le - binaire, quel que soit
le contexte.

> En C, je m'attendrais à ce que - a * b et 0 - a * b donnent la même
> chose (en supposant a * b non nul), mais si le mode d'arrondi est
> vers -inf ou +inf, il peut y avoir une différence.

Ceci montre bien la différence entre les maths et l'informatique...

Il ne devrait pas y avoir de différence (sauf évidente). Ou alors il
ne faut pas chercher à utiliser les mêmes opérateurs (en particulier,
le / pour la division entière est un mauvais choix).

--
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Dans l'article <4c88ff61$0$4051$426a74cc@news.free.fr>,
Samuel DEVULDER <samuel-dot-devulder@laposte-dot-com> écrit:

En attendant que Vicent confirme ou infirme.. j'ai rapidement lu le PS
(arg.. de nos jour c'est PDF le standard) de la lib. Si j'ai pas tout
compris de travers, en fait il n'y a pas de test à ZERO et on ne peut
décider de l'égalité de deux REELS. Il n'y a que des tests de proximité
entre 2 réels avec tolérance. Idem pour les signes.

C'est ça, en gros, pas de fonction discontinue.

Cette bibliothèque est marante car en fait si en cours de route il se
rend compte qu'il ne peut pas avoir la bonne précision pour décider un
test, elle fait alors un longjmp en début de prog et le rejoue avec une
précision augmentée. Je trouve l'idée rigolote (il fallait oser), mais
ca doit conduire à des perfs désastreuses et des effets spéciaux sur les
IO. Du coup on a pas le droit d'utiliser les IO ni le malloc ni pleins
d'autres trucs avec cette bibliothèque. Son usage en est donc forcément
réduit.

Les perf étaient bonnes. iRRAM avait d'ailleurs fini 3e à la
compétition Many Digits:

http://homepages.cwi.nl/~milad/manydigits/results.html

Là où j'ai un doute sur ma lecture c'est que Vincent a parlé de l'arbre
de calcul.. Or en survolant la doc, j'ai plutôt eu l'impression que
l'arbre de calcul c'est l'exécutable lui même et que iRRAM ne fait que
maintenir les calculs à la bonne précision avec le longjmp magique qui
fait refaire toute l'exécution du programme (donc tout le calcul) avec
une précisions augmentée en cas de soucis. Là ou ca colle pas avec
l'idée de l'arbre de calcul que j'imaginais symbolique, c'est que s'il
était maintenu dans les objets REELS, il aurait suffit de tout
ré-évaluer avec une meilleurs précision sans faire rejouer le prog
depuis le début.

Il me semblait que c'était l'arbre de calcul. Mais rejouer le programme
est probablement plus efficace en cas de grosses boucles ou appels
récursifs.

Peut-être qu'en fait c'est lié au fait que le rejeu ne serait pas
suffisant car avec une meilleure précision l'arbre de calcul doit
probablement devenir faux. Par exemple si on double le nombre de digits,
les méthodes quadratiques de calcul utilisée par la bibliothèque telle
que sqrt() ou l'inversion de nombre devront faire une passe de plus, et
donc l'arbre augmenter d'un niveau, invalidant l'arbre précédent. Ouais
ca doit être un truc dans ce goût là.

Tout dépend des opérations qu'on s'autorise. Si on ne fait pas de
test lié à la précision, l'arbre de calcul doit rester correct.

--
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Le 11/09/2010 14:44, Vincent Lefevre a écrit :

Les perf étaient bonnes. iRRAM avait d'ailleurs fini 3e à la
compétition Many Digits:

http://homepages.cwi.nl/~milad/manydigits/results.html

Cette compétition mesure les perfs des calculs en grande précision? Donc
ca n'a peut-être pas évalué le cout de re-jeu pour IRRAM. En gros si la
précision requise dans les 1er pas de l'algo est suffisante, il n'est
pas dans le pire cas ou arrivé quasi à la fin il se rend compte qu'il
doit tout redérouler depuis le début en doublant le nb de digits... et
faire ca plusieurs fois car la précision finale nécéssiterait un nb
faramineux de digits après la virgule pour décider, bien plus de digits
que n'en nécessite le résultat final.

De toute façon IRRAM utilise une bonne bibliothèque pour les calculs
multi-précision. Donc ses perfs ne peuvent pas être trop mauvaise vis
avis de l'état de l'art pour les opérations élémentaires ne nécéssitant
pas de redérouler l'algo depuis le début.

Tout dépend des opérations qu'on s'autorise. Si on ne fait pas de
test lié à la précision, l'arbre de calcul doit rester correct.

Je pense que l'opérateur "limite" change le fonctionnement du prog.
Intrinsèquement cet opérateur est la définition classique de la limite:
pour tout epsilon (petit=précision), il existe un N tel que... Donc si
on change la précision on doit changer le N, et typiquement dérouler la
boucle de calcul une ou 2 fois de plus en fonction de la convergence de
l'algo utilisé. Au final l'arbre de calcul change de forme à chaque
redémarrage du prog.

sam.

Vincent Lefevre a écrit :

Dans l'article <4c88d1a6$0$5417$ba4acef3@reader.news.orange.fr>,
Wykaaa <wykaaa@yahoo.fr> écrit:

Il ne faut pas oublier qu'on souhaite, en général, que les langages de
programmation courants soient de type 2 de Chomsky (langages
context-free analysables par des automates à pile). Si on introduit une
précédence différente pour le - unaire utilisé sur une expression
"puissance", je ne suis pas certain qu'on reste "context-free" et les
langages de type 1 (contextuels) ne sont analysables que par des AMLB
(automates à mémoire linéairement bornée) ce qui devient assez
impraticable pour des programmes "réalistes".

Je ne parle pas de mettre une précédence différente, mais d'avoir
systématiquement la même précédence que le - binaire, quel que soit
le contexte.

Je n'ai pas analysé finement mais il me semble que ça poserait d'autres
problèmes en C avec l'opérateur -- (décrément) entre autre dans
certaines expressions ou même en combinant le - unaire et le moins
binaire. et comme l'opérateur "puissance" n'existe pas en C, pourquoi se
compliquer la vie ?

En C, je m'attendrais à ce que - a * b et 0 - a * b donnent la même
chose (en supposant a * b non nul), mais si le mode d'arrondi est
vers -inf ou +inf, il peut y avoir une différence.

Ceci montre bien la différence entre les maths et l'informatique...

Il ne devrait pas y avoir de différence (sauf évidente). Ou alors il
ne faut pas chercher à utiliser les mêmes opérateurs (en particulier,
le / pour la division entière est un mauvais choix).

Je suis assez d'accord sur ce point mais, pour un langage donné, il n'y
a pas LA sémantique mais une sémantique. K&R ont fait un choix pour le
langage C...
Il ne faut pas oublier les règles de conversions implicites quand on
mélange des types dans une expression en C (char en int est assez
absurde en soi également mais ça "rend" bien des services...).