Priorité et associativité des opérateurs

espie

11/09/2010 à 23:38

In article <4c8bc2c5$0$23150$,
Samuel DEVULDER wrote:

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.

Oui, et ? on parle ici du cout reel pour faire un calcul donne, avec un
bench qui n'a pas ete etudie pour "resister" ou pour "favoriser" IRRAM.
Si cette bibliotheque s'en sort bien, ca veut dire que le postulat de base
etait une bonne idee, au moins dans le contexte de ce bench.

Intuitivement, on se fiche un peu du cout du rejeu, si ce rejeu est peu
frequent. IRRAM fait le pari que souvent, on va obtenir un resultat avec
peu de rejeu, donc tres vite. C'est de l'algo 'stochastique'. Je ne sais
pas si quelqu'un s'est amuse a faire une analyse en moyenne de ce
comportement, mais je vois au moins deux methodes utilisees super-souvent
(Monte-Carlo et le recuit simule) ou on fait un peu le meme type de pari,
et ou on torsche regulierement des algo exacts dans des cas utiles...

Samuel DEVULDER

12/09/2010 à 01:19

Le 11/09/2010 23:38, Marc Espie a écrit :

In article<4c8bc2c5$0$23150$,
Samuel DEVULDER wrote:
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.

Oui, et ?

Et il faut refaire le calcul depuis le début, et toutes les zones
mémoires alloues par malloc() restent perdues dans le tas, les thread
non proprement fermes, les fichiers non remis au départ etc. Bref ca
limite fortement l'inclusion de cette bibliothèque dans un prog un peu
complexe.

on parle ici du cout reel pour faire un calcul donne, avec un

bench qui n'a pas ete etudie pour "resister" ou pour "favoriser" IRRAM.
Si cette bibliotheque s'en sort bien, ca veut dire que le postulat de base
etait une bonne idee, au moins dans le contexte de ce bench.

Oui c'est clair. D'ailleurs les evals sur benchs standardisés sont un
sujet en soi. Il peuvent biaiser les prog pour ne traiter que les
problèmes du bench. Par contre même si le bench ne favorise pas tel ou
telle bibliothèque, les candidats sont ceux qui ont développés la
bibliothèque, et donc des gens qui maitrisent à fond leur outil. Il
serait intéressant de savoir si des non spécialistes arriveraient à des
résultats aussi bons. Bref, une notion de bench par le "quidam moyen"
qui permet de mesurer si la bibliothèque aide beaucoup son utilisateur
ou si le bon classement de la bibliothèque revient exclusivement à
l'excellente technicité des candidats au concours.

En tout cas l'idée du prog qui se recalibre et se relance est rigolote.
J'aime bien.

Intuitivement, on se fiche un peu du cout du rejeu, si ce rejeu est peu
frequent. IRRAM fait le pari que souvent, on va obtenir un resultat avec
peu de rejeu, donc tres vite. C'est de l'algo 'stochastique'. Je ne sais
pas si quelqu'un s'est amuse a faire une analyse en moyenne de ce
comportement, mais je vois au moins deux methodes utilisees super-souvent
(Monte-Carlo et le recuit simule) ou on fait un peu le meme type de pari,
et ou on torsche regulierement des algo exacts dans des cas utiles...

La complexité d'une tel algo serait intéressante en fonction de la
précision voulue sachant qu'à chaque fois qu'elle augmente, les calculs
intermédiaires sont de plus en plus couteux. Les algos stochastiques ne
doivent pas chercher très loin après la virgules, alors que les biblio
multi-précision doivent pouvoir aller super-loin efficacement. Le bench
évoqué ne teste que les 10 000 ou 100 000 premières décimales après la
virgule, c'est déjà pas mal, mais on peut demander bcp plus d'une
gestion formelle des expressions. Par exemple jusqu'à combien de chiffre
après la virgule faut il calculer
(phi^n - (-1/phi)^n) / sqrt(5)
Pour s'apercevoir qu'il est entier? En fait il l'est mais pour le
décider il faut savoir travailler avec les extensions algèbriques. Cela
semble être hors de porté de IRRAM qui ne sait finalement *pas*
représenter exactement sqrt(2), sqrt(5) ou phi (c'était le point de
départ de ce fil). Il sait uniquement l'évaluer avec suffisamment de
précision. Ca n'est pas strictement équivalent, mais pas inintéressant
non plus.

A propos de C, de multi-précision et de vraiment beaucoup, mais beaucoup
de chiffres après la virgule, on peut évoquer le dernier résultat de
Bellard: le record du monde (avant Aout 2010) de chiffres après la
virgule pour PI sur un ordinateur de bureau.
http://bellard.org/pi/pi2700e9/
http://bellard.org/pi/pi2700e9/pipcrecord.pdf

En vlà un gars qui s'ammuse avec la programmation en C. Déjà il s'est
refait un emacs et un compilo C compatible GCC.. en bcp bcp plus petit
et rapide. Mais en plus il fait des trucs rigolo comme émettre une
chaine TNT en allumant des pixels sur un écran CRT. C'est pas de la
programmation, c'est de l'art. Chapeau l'artiste!

sam.

Le 11/09/2010 23:38, Marc Espie a écrit :

In article<4c8bc2c5$0$23150$426a74cc@news.free.fr>,
Samuel DEVULDER<samuel-dot-devulder@laposte-dot-com> wrote:

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.

Oui, et ?

Et il faut refaire le calcul depuis le début, et toutes les zones
mémoires alloues par malloc() restent perdues dans le tas, les thread
non proprement fermes, les fichiers non remis au départ etc. Bref ca
limite fortement l'inclusion de cette bibliothèque dans un prog un peu
complexe.

on parle ici du cout reel pour faire un calcul donne, avec un

bench qui n'a pas ete etudie pour "resister" ou pour "favoriser" IRRAM.
Si cette bibliotheque s'en sort bien, ca veut dire que le postulat de base
etait une bonne idee, au moins dans le contexte de ce bench.

Oui c'est clair. D'ailleurs les evals sur benchs standardisés sont un
sujet en soi. Il peuvent biaiser les prog pour ne traiter que les
problèmes du bench. Par contre même si le bench ne favorise pas tel ou
telle bibliothèque, les candidats sont ceux qui ont développés la
bibliothèque, et donc des gens qui maitrisent à fond leur outil. Il
serait intéressant de savoir si des non spécialistes arriveraient à des
résultats aussi bons. Bref, une notion de bench par le "quidam moyen"
qui permet de mesurer si la bibliothèque aide beaucoup son utilisateur
ou si le bon classement de la bibliothèque revient exclusivement à
l'excellente technicité des candidats au concours.

En tout cas l'idée du prog qui se recalibre et se relance est rigolote.
J'aime bien.

Intuitivement, on se fiche un peu du cout du rejeu, si ce rejeu est peu
frequent. IRRAM fait le pari que souvent, on va obtenir un resultat avec
peu de rejeu, donc tres vite. C'est de l'algo 'stochastique'. Je ne sais
pas si quelqu'un s'est amuse a faire une analyse en moyenne de ce
comportement, mais je vois au moins deux methodes utilisees super-souvent
(Monte-Carlo et le recuit simule) ou on fait un peu le meme type de pari,
et ou on torsche regulierement des algo exacts dans des cas utiles...

La complexité d'une tel algo serait intéressante en fonction de la
précision voulue sachant qu'à chaque fois qu'elle augmente, les calculs
intermédiaires sont de plus en plus couteux. Les algos stochastiques ne
doivent pas chercher très loin après la virgules, alors que les biblio
multi-précision doivent pouvoir aller super-loin efficacement. Le bench
évoqué ne teste que les 10 000 ou 100 000 premières décimales après la
virgule, c'est déjà pas mal, mais on peut demander bcp plus d'une
gestion formelle des expressions. Par exemple jusqu'à combien de chiffre
après la virgule faut il calculer
(phi^n - (-1/phi)^n) / sqrt(5)
Pour s'apercevoir qu'il est entier? En fait il l'est mais pour le
décider il faut savoir travailler avec les extensions algèbriques. Cela
semble être hors de porté de IRRAM qui ne sait finalement *pas*
représenter exactement sqrt(2), sqrt(5) ou phi (c'était le point de
départ de ce fil). Il sait uniquement l'évaluer avec suffisamment de
précision. Ca n'est pas strictement équivalent, mais pas inintéressant
non plus.

A propos de C, de multi-précision et de vraiment beaucoup, mais beaucoup
de chiffres après la virgule, on peut évoquer le dernier résultat de
Bellard: le record du monde (avant Aout 2010) de chiffres après la
virgule pour PI sur un ordinateur de bureau.
http://bellard.org/pi/pi2700e9/
http://bellard.org/pi/pi2700e9/pipcrecord.pdf

En vlà un gars qui s'ammuse avec la programmation en C. Déjà il s'est
refait un emacs et un compilo C compatible GCC.. en bcp bcp plus petit
et rapide. Mais en plus il fait des trucs rigolo comme émettre une
chaine TNT en allumant des pixels sur un écran CRT. C'est pas de la
programmation, c'est de l'art. Chapeau l'artiste!

sam.

Vous avez filtré cet utilisateur ! Consultez son message

Le 11/09/2010 23:38, Marc Espie a écrit :

In article<4c8bc2c5$0$23150$,
Samuel DEVULDER wrote:
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.

Oui, et ?

Et il faut refaire le calcul depuis le début, et toutes les zones
mémoires alloues par malloc() restent perdues dans le tas, les thread
non proprement fermes, les fichiers non remis au départ etc. Bref ca
limite fortement l'inclusion de cette bibliothèque dans un prog un peu
complexe.

on parle ici du cout reel pour faire un calcul donne, avec un

bench qui n'a pas ete etudie pour "resister" ou pour "favoriser" IRRAM.
Si cette bibliotheque s'en sort bien, ca veut dire que le postulat de base
etait une bonne idee, au moins dans le contexte de ce bench.

Oui c'est clair. D'ailleurs les evals sur benchs standardisés sont un
sujet en soi. Il peuvent biaiser les prog pour ne traiter que les
problèmes du bench. Par contre même si le bench ne favorise pas tel ou
telle bibliothèque, les candidats sont ceux qui ont développés la
bibliothèque, et donc des gens qui maitrisent à fond leur outil. Il
serait intéressant de savoir si des non spécialistes arriveraient à des
résultats aussi bons. Bref, une notion de bench par le "quidam moyen"
qui permet de mesurer si la bibliothèque aide beaucoup son utilisateur
ou si le bon classement de la bibliothèque revient exclusivement à
l'excellente technicité des candidats au concours.

En tout cas l'idée du prog qui se recalibre et se relance est rigolote.
J'aime bien.

Intuitivement, on se fiche un peu du cout du rejeu, si ce rejeu est peu
frequent. IRRAM fait le pari que souvent, on va obtenir un resultat avec
peu de rejeu, donc tres vite. C'est de l'algo 'stochastique'. Je ne sais
pas si quelqu'un s'est amuse a faire une analyse en moyenne de ce
comportement, mais je vois au moins deux methodes utilisees super-souvent
(Monte-Carlo et le recuit simule) ou on fait un peu le meme type de pari,
et ou on torsche regulierement des algo exacts dans des cas utiles...

La complexité d'une tel algo serait intéressante en fonction de la
précision voulue sachant qu'à chaque fois qu'elle augmente, les calculs
intermédiaires sont de plus en plus couteux. Les algos stochastiques ne
doivent pas chercher très loin après la virgules, alors que les biblio
multi-précision doivent pouvoir aller super-loin efficacement. Le bench
évoqué ne teste que les 10 000 ou 100 000 premières décimales après la
virgule, c'est déjà pas mal, mais on peut demander bcp plus d'une
gestion formelle des expressions. Par exemple jusqu'à combien de chiffre
après la virgule faut il calculer
(phi^n - (-1/phi)^n) / sqrt(5)
Pour s'apercevoir qu'il est entier? En fait il l'est mais pour le
décider il faut savoir travailler avec les extensions algèbriques. Cela
semble être hors de porté de IRRAM qui ne sait finalement *pas*
représenter exactement sqrt(2), sqrt(5) ou phi (c'était le point de
départ de ce fil). Il sait uniquement l'évaluer avec suffisamment de
précision. Ca n'est pas strictement équivalent, mais pas inintéressant
non plus.

A propos de C, de multi-précision et de vraiment beaucoup, mais beaucoup
de chiffres après la virgule, on peut évoquer le dernier résultat de
Bellard: le record du monde (avant Aout 2010) de chiffres après la
virgule pour PI sur un ordinateur de bureau.
http://bellard.org/pi/pi2700e9/
http://bellard.org/pi/pi2700e9/pipcrecord.pdf

En vlà un gars qui s'ammuse avec la programmation en C. Déjà il s'est
refait un emacs et un compilo C compatible GCC.. en bcp bcp plus petit
et rapide. Mais en plus il fait des trucs rigolo comme émettre une
chaine TNT en allumant des pixels sur un écran CRT. C'est pas de la
programmation, c'est de l'art. Chapeau l'artiste!

sam.

Tonton Th

12/09/2010 à 03:00

On 09/09/2010 11:17 AM, Pierre Maurette wrote:

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.

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.

Les deux, mon général.

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

Vincent Lefevre

14/09/2010 à 11:07

Dans l'article <4c8bf275$0$5418$,
Wykaaa écrit:

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.

Je ne vois pas pourquoi. Un exemple?

et comme l'opérateur "puissance" n'existe pas en C, pourquoi se
compliquer la vie ?

Parce que le problème existe aussi pour le - unaire, quand on
travaille avec des modes d'arrondi dirigés (même si le fait d'avoir
un mode d'arrondi global et non attaché à chaque opération est une
mauvaise idée).

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

Le pire, c'est quand un type signé est converti implicitement en
non signé: la valeur peut être complètement changée.

--
Vincent Lefèvre - 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)

Vincent Lefevre

14/09/2010 à 11:13

Dans l'article <4c8bc2c5$0$23150$,
Samuel DEVULDER écrit:

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.

Noter tout de même que pour certaines fonctions (sin?), iRRAM (qui
n'utilise/n'utilisait que les fonctions de base de MPFR) était plus
rapide que MPFR. Je ne sais pas si ça a changé. Certaines fonctions
de MPFR ont été améliorées depuis...

--
Vincent Lefèvre - 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)

Vincent Lefevre

14/09/2010 à 11:19

Dans l'article <i6gst7$nlv$,
Marc Espie écrit:

Oui, et ? on parle ici du cout reel pour faire un calcul donne, avec un
bench qui n'a pas ete etudie pour "resister" ou pour "favoriser" IRRAM.
Si cette bibliotheque s'en sort bien, ca veut dire que le postulat de base
etait une bonne idee, au moins dans le contexte de ce bench.

Tout à fait.

Intuitivement, on se fiche un peu du cout du rejeu, si ce rejeu est peu
frequent. IRRAM fait le pari que souvent, on va obtenir un resultat avec
peu de rejeu, donc tres vite. C'est de l'algo 'stochastique'. Je ne sais
pas si quelqu'un s'est amuse a faire une analyse en moyenne de ce
comportement, mais je vois au moins deux methodes utilisees super-souvent
(Monte-Carlo et le recuit simule) ou on fait un peu le meme type de pari,
et ou on torsche regulierement des algo exacts dans des cas utiles...

C'est aussi ce qui se passe pour l'arrondi correct avec MPFR: si on
tombe sur un cas "difficile à arrondir" (ce qui est censé être très
rare), il faut refaire tous les calculs à une plus grande précision
(stratégie dite de Ziv). Mais comme ces cas sont censés être rares,
cela ne pose pas de problème pour le temps de calcul moyen.

Maintenant, à cause de cancellations dans les calculs internes, il
se peut que l'on ait à refaire les calculs plus souvent que prévu
dans certains domaines. Mais c'est considéré comme un bug (enfin, au
sens d'absence d'optimisation) dans MPFR, et ces cas sont corrigés
quand ils sont découverts, en augmentant la précision de départ en
fonction de la valeur de l'entrée, par exemple.

--
Vincent Lefèvre - 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)

Vincent Lefevre

14/09/2010 à 11:29

Dans l'article <4c8c0e7f$0$18994$,
Samuel DEVULDER écrit:

La complexité d'une tel algo serait intéressante en fonction de la
précision voulue sachant qu'à chaque fois qu'elle augmente, les calculs
intermédiaires sont de plus en plus couteux. Les algos stochastiques ne
doivent pas chercher très loin après la virgules, alors que les biblio
multi-précision doivent pouvoir aller super-loin efficacement. Le bench
évoqué ne teste que les 10 000 ou 100 000 premières décimales après la
virgule, c'est déjà pas mal, mais on peut demander bcp plus d'une
gestion formelle des expressions. Par exemple jusqu'à combien de chiffre
après la virgule faut il calculer
(phi^n - (-1/phi)^n) / sqrt(5)
Pour s'apercevoir qu'il est entier? En fait il l'est mais pour le
décider il faut savoir travailler avec les extensions algèbriques. Cela
semble être hors de porté de IRRAM qui ne sait finalement *pas*
représenter exactement sqrt(2), sqrt(5) ou phi (c'était le point de
départ de ce fil). Il sait uniquement l'évaluer avec suffisamment de
précision. Ca n'est pas strictement équivalent, mais pas inintéressant
non plus.

iRRAM sait représenter sqrt(2), sqrt(5)... exactement: par un programme.
Mais cette forme introduit une limitation: les fonctions discontinues
ne sont pas supportées en général, et en particulier les problèmes de
décision, du style: est-ce que tel nombre est un entier?

C'est la même chose en math: sqrt(2) est représenté exactement par
une expression: sqrt(2). On peut faire des calculs plus puisssants
qu'avec iRRAM. Mais certains problèmes restent indécidables.

--
Vincent Lefèvre - 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)

Samuel DEVULDER

14/09/2010 à 12:32

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

iRRAM sait représenter sqrt(2), sqrt(5)... exactement: par un programme.

Oui sauf que sa représentation se limite au calcul numérique. Il ne sait
pas manipuler symboliquement sqrt(2). Typiquement la valeur du test
sqrt(2)*sqrt(2) == 2 lui est à tout jamais inconnue. Il peut juste
approximer 2.000000000... sans jamais en être sur que ce soit exactement
2: il part en boucle infinie. Pour éviter cela il faudrait travailler au
niveau supérieur, "méta", et voir que la limite du calcul de l'algo
sqrt(x) multiplié par lui même est exactement x quel que soit ce dernier
nombre (positif tout de même).

Mais cette forme introduit une limitation: les fonctions discontinues
ne sont pas supportées en général, et en particulier les problèmes de
décision, du style: est-ce que tel nombre est un entier?

Le test à nul est aussi affecté sans avoir besoin de notion d'entier.
Par exemple Si y!=nul et x = sqrt(y) est-ce que "x/y - 1/x est nul" ne
peut être décidé par iRRAM. D'autres outils travaillant à un autre
niveau savent le faire.

C'est la même chose en math: sqrt(2) est représenté exactement par
une expression: sqrt(2). On peut faire des calculs plus puisssants
qu'avec iRRAM. Mais certains problèmes restent indécidables.

Ca pose la question de fond qui est limite philosophique. Qu'est ce que
sqrt(2) ? Une valeur symbolique munie de quelques propriétés? Une valeur
numérique infiniment approximables? Une suite de rationnels qui converge
vers lui et dont les termes pairs et impairs l'encadrent? La suite de
ses chiffres dans son développement décimal? La suite des entiers
utilisés dans son développement en fraction continue? Un élément de
l'extension algèbrique de RootOf(X^2-2)?

Un langage rationnel?

Un peu tout ca en fait. D'ailleurs il me semble qu'on peut montrer que
les nombres des extensions algébriques ont une décomposition en fraction
continue qui est reconnaissable par un automate à état finis. Ca fait
réflechir: ne sait on finalement manipuler exactement que des choses
qu'un automate assez simple serait reconnaitre? Vaste question!

Quoi qu'on en pense, tu as raison aucun outil ne peut être universel.
Ils ont tous des limites et cela doit être une conséquence des théorèmes
de complétude et d'indécidabilité des systèmes formels je suppose.

sam.

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

iRRAM sait représenter sqrt(2), sqrt(5)... exactement: par un programme.

Oui sauf que sa représentation se limite au calcul numérique. Il ne sait
pas manipuler symboliquement sqrt(2). Typiquement la valeur du test
sqrt(2)*sqrt(2) == 2 lui est à tout jamais inconnue. Il peut juste
approximer 2.000000000... sans jamais en être sur que ce soit exactement
2: il part en boucle infinie. Pour éviter cela il faudrait travailler au
niveau supérieur, "méta", et voir que la limite du calcul de l'algo
sqrt(x) multiplié par lui même est exactement x quel que soit ce dernier
nombre (positif tout de même).

Mais cette forme introduit une limitation: les fonctions discontinues
ne sont pas supportées en général, et en particulier les problèmes de
décision, du style: est-ce que tel nombre est un entier?

Le test à nul est aussi affecté sans avoir besoin de notion d'entier.
Par exemple Si y!=nul et x = sqrt(y) est-ce que "x/y - 1/x est nul" ne
peut être décidé par iRRAM. D'autres outils travaillant à un autre
niveau savent le faire.

C'est la même chose en math: sqrt(2) est représenté exactement par
une expression: sqrt(2). On peut faire des calculs plus puisssants
qu'avec iRRAM. Mais certains problèmes restent indécidables.

Ca pose la question de fond qui est limite philosophique. Qu'est ce que
sqrt(2) ? Une valeur symbolique munie de quelques propriétés? Une valeur
numérique infiniment approximables? Une suite de rationnels qui converge
vers lui et dont les termes pairs et impairs l'encadrent? La suite de
ses chiffres dans son développement décimal? La suite des entiers
utilisés dans son développement en fraction continue? Un élément de
l'extension algèbrique de RootOf(X^2-2)?

Un langage rationnel?

Un peu tout ca en fait. D'ailleurs il me semble qu'on peut montrer que
les nombres des extensions algébriques ont une décomposition en fraction
continue qui est reconnaissable par un automate à état finis. Ca fait
réflechir: ne sait on finalement manipuler exactement que des choses
qu'un automate assez simple serait reconnaitre? Vaste question!

Quoi qu'on en pense, tu as raison aucun outil ne peut être universel.
Ils ont tous des limites et cela doit être une conséquence des théorèmes
de complétude et d'indécidabilité des systèmes formels je suppose.

sam.

Vous avez filtré cet utilisateur ! Consultez son message

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

iRRAM sait représenter sqrt(2), sqrt(5)... exactement: par un programme.

Oui sauf que sa représentation se limite au calcul numérique. Il ne sait
pas manipuler symboliquement sqrt(2). Typiquement la valeur du test
sqrt(2)*sqrt(2) == 2 lui est à tout jamais inconnue. Il peut juste
approximer 2.000000000... sans jamais en être sur que ce soit exactement
2: il part en boucle infinie. Pour éviter cela il faudrait travailler au
niveau supérieur, "méta", et voir que la limite du calcul de l'algo
sqrt(x) multiplié par lui même est exactement x quel que soit ce dernier
nombre (positif tout de même).

Mais cette forme introduit une limitation: les fonctions discontinues
ne sont pas supportées en général, et en particulier les problèmes de
décision, du style: est-ce que tel nombre est un entier?

Le test à nul est aussi affecté sans avoir besoin de notion d'entier.
Par exemple Si y!=nul et x = sqrt(y) est-ce que "x/y - 1/x est nul" ne
peut être décidé par iRRAM. D'autres outils travaillant à un autre
niveau savent le faire.

C'est la même chose en math: sqrt(2) est représenté exactement par
une expression: sqrt(2). On peut faire des calculs plus puisssants
qu'avec iRRAM. Mais certains problèmes restent indécidables.

Ca pose la question de fond qui est limite philosophique. Qu'est ce que
sqrt(2) ? Une valeur symbolique munie de quelques propriétés? Une valeur
numérique infiniment approximables? Une suite de rationnels qui converge
vers lui et dont les termes pairs et impairs l'encadrent? La suite de
ses chiffres dans son développement décimal? La suite des entiers
utilisés dans son développement en fraction continue? Un élément de
l'extension algèbrique de RootOf(X^2-2)?

Un langage rationnel?

Un peu tout ca en fait. D'ailleurs il me semble qu'on peut montrer que
les nombres des extensions algébriques ont une décomposition en fraction
continue qui est reconnaissable par un automate à état finis. Ca fait
réflechir: ne sait on finalement manipuler exactement que des choses
qu'un automate assez simple serait reconnaitre? Vaste question!

Quoi qu'on en pense, tu as raison aucun outil ne peut être universel.
Ils ont tous des limites et cela doit être une conséquence des théorèmes
de complétude et d'indécidabilité des systèmes formels je suppose.

sam.

Wykaaa

14/09/2010 à 12:48

Vincent Lefevre a écrit :

Dans l'article <4c8bf275$0$5418$,
Wykaaa écrit:

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.

Je ne vois pas pourquoi. Un exemple?

et comme l'opérateur "puissance" n'existe pas en C, pourquoi se
compliquer la vie ?

Parce que le problème existe aussi pour le - unaire, quand on
travaille avec des modes d'arrondi dirigés (même si le fait d'avoir
un mode d'arrondi global et non attaché à chaque opération est une
mauvaise idée).

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

Le pire, c'est quand un type signé est converti implicitement en
non signé: la valeur peut être complètement changée.

Pour résumer ma position, je suis toujours pour mettre des parenthèses
dans les expressions et expliciter TOUTES les conversions (comme ADA
l'impose, par exemple).

espie

14/09/2010 à 17:07

In article <4c8f4f39$0$12643$,
Samuel DEVULDER wrote:

Un peu tout ca en fait. D'ailleurs il me semble qu'on peut montrer que
les nombres des extensions algébriques ont une décomposition en fraction
continue qui est reconnaissable par un automate à état finis. Ca fait
réflechir: ne sait on finalement manipuler exactement que des choses
qu'un automate assez simple serait reconnaitre? Vaste question!

Pas si vaste que ca, en fait. Bienvenue dans le monde merveilleux de la
calculabilite. Un des vieux resultats (deprimants) dont je me souviens,
c'est que les problemes se divisent essentiellement en 2:
- les problemes triviaux (e.g, assimilables a des automates simples)
- les problemes insolubles.

c'est toujours la porte sur la demonstration (fausse) de P!=NP qui a fait
couler de l'encre recemment: on finira bien par comprendre pourquoi les
problemes polynomiaus ont une facheuse tendance a s'ecrire n^p, avec p petit,
et pourquoi les algos en n^2010 ne courent pas les rues...

Priorité et associativité des opérateurs

10 réponses

Veuillez sélectionner un problème