Discussion :

[souviron34]

Les fameuses 4000 lignes implémentent de façon exacte les quelques lignes suivantes de votre lien:

Je ne parlais pas pour vous, mais à propos de

Pour trouver les coordonnées du point d'intersection, l'algorithme emploi une division pour calculer chaque pente et une troisième division pour l'abscisse. Cela provoque une perte de précision. De fait, on ne peux pas estimer que le point d'intersection se trouve sur la droite, quelque soit la precision de notre repère.

Maintenant, sur le fond...


Dans le lien que vous donnez, je lis dans le premier paragraphe :

and if a fourth line misses this point by 1.0e-380, then it also misses it in CGAL

Or ceci est la précision des nombres double-précision..

Pourquoi donc penser que quelque chose est plus précis alors que les routines données dans les liens utilisent des nombres double-précision ?????????


Si on utilise des double-précisions, on obtient instantanément avec les formules données ci-dessus la précision indiquée par CGAL...

Je ne vois rien de particulier là-dedans... Et sans en faire 4000 lignes....

Si il y a un message que j'aimerais faire passer dans cette discussion, c'est que l'exactitude est un problème très difficile et fortement sous-estimé.

Là nous sommes d'accord.

Par contre je reste perlexe quand je lis :

pour une simple addition de flottant, on peut avoir des choses étonnantes, comme une perte de topologie par déplacement. C'est un problème concret qu'on retrouve dans des applications aussi peu exotiques que les pièces avion, qui après exportation sous format CNC sont topologiquement correctes si elles sont exportées dans le repère de conception, mais incorrectes (trous, plis, etc.) si elles sont exportées en coordonnées avion.

Ce que je vois ici est une précision de format de sortie, je ne vois pas en quoi la précision des CALCULS est impliquée...


Car, même si par exemple on pouvait usiner des pièces à l'Angstrom près, cela resterait quand même de l'odre de e-10...

Comme ce n'est pas le cas (surtout pour des pièces d'avion), je ne vois pas en quoi une précision supérieure à e-10 serait nécessaire...


Cela me fait penser à la maladie de l'utilisation des bibliothèques de "grands nombres"...

Comme je l'avais dit dans un autre post sur ce sujet, si l'on prend la taille de l'univers et qu'on la mette en Angstrom, on n'arrive QUE à e20..

Or, étant donné que la précision sur la mesure (les 13.7 milliards d'années-lumière) est de l'ordre de 1% de 1 milliard d'années-lumière, utiliser une précisionde e20 est stupide et FAUX...


Pour votre problème, plutôt que d'utliser 4000 lignes pour faire quelque chose qu'on peut faire en 4, il serait plutôt bien de travailler en précision relative.


C'est le point central, et le point pour lequel le post de ben.oeilnoir est absurde également....


Admettons que je fasse des calculs géodésiques sur la Terre : 40 000 km soit 40 000 000 mètres..

Admettons que l'on veuille aller jusqu'à une précision du micron (ce qui est dans la réalité absurde, mais pas si par exemple on veut mesure la distance Terre-Lune).

Cela n'amène qu'à un facteur de e13.

Si ce qu'on mesure ce sont des différences, il suffit par exemple de considérer à l'intérieur d'un mètre (ou décimètre), s'affranchissant donc d'un facteur e7 (e8)... Et si ce ne sont pas des différences, avoir une précision du micron sur une distance de 40 millions de mètres est absurde...

Et donc on n'arrive QUE à e5 ou e6..


Avec des calculs en double précision, ceci est très largement atteint sans rin faire de paticulier....



J'avoue être extrêmement perpelexe quant à l'utilité de dériver une usine à gaz pour obtenir des choses qui d'une part n'ont aucun sesn dans la réalité, et qui d'autre part négligent le problème de fond...


J'aimerais beaucoup que vous me montriez un exemple réel du pourquoi vous auriez besoin de "en 80 bits sur architecture x86). 4000 lignes pour dire si un point est à droite ou à gauche d'un segment peut paraître impressionnant" et en quoi c'est "plus exact" que le calcul en double-précision simple...



PS: dans mes calculs, je force même une précision relative de e-8 piur l'égalité entre 2 nombres...

[ac_wingless]

Comme quoi cette discussion apparemment triviale peut mettre en lumière des points intéressants!
Vous mettez le doigt sur exactement le problème que souhaite résoudre CGAL ainsi que toute la littérature sur la géométrie algorithmique. Là où je suis embêté c'est quand les grands spécialistes (dont je ne fais pas partie) l'expliquent dans les liens, et qu'après lecture vous me demandez de le ré-expliquer

Mais soit, ce que je peux faire c'est citer des exemples un peu plus concrets que les assertions académiques des universitaires cités.
Par exemple pour les pièces avion, elles sont usinées. L'usinage passe toujours par une phase de compensation d'outil, qui va s'appuyer sur la géométrie connue par la machine d'usinage. Ces corrections s'appliquent en général selon la normale des facettes (souvent des triangles pour les procédés en bout de chaine: normalement à ce stade on n'a plus besoin de surfaces complexes). Un des formats les plus universels est le "STL", qui est un simple sac de triangles en simple précision. La simple précision peut stocker 23 bits de mantisse dans la puissance de 2 courante, mais bien sûr comme la virgule est flottante, on peut tout de même très bien stocker une précision de l'ordre de l'angström si l'unité est le mm. Sauf que si on passe en coordonnées avion on ajoute par exemple 16m (soit 16000 unités élémentaires), et on "gâche" 14 bits sur les 23. Donc le nombre voit en fait son exposant changer lors de l'addition, de manière à ce que la mantisse soit toujours utilisée le plus efficacement possible. Malheureusement, cela a pour conséquence que la plus petite dimension adressable est multipliée d'autant. Comme 23 bits représentent 8 millions de valeurs, dans une certaine zone des coordonnées avion on n'a plus qu'une précision de l'ordre de 8 µm.

Jusque là, on se trouve dans la bête erreur de chute que l'ingénierie partage avec la comptabilité. Les solutions existent, comme tout simplement faire les calculs avant l'exportation (rien que ça, dans la réalité, c'est quasiment impossible, mais cette fois pour des raisons administratives dont la difficulté dépasse très largement les défis auxquels les ingénieurs sont habitués).

Par contre on commence à soupçonner les problèmes qu'adresse CGAL et consorts: quid de la normale d'un triangle dont les sommets sont bougés de 8 µm? Si le triangle est assez grand, pas de souci, l'erreur sera certes très importantes en degrés (bien au delà des problèmes dus strictement à la précision de représentation en simple ou double précision), mais on ne devrait pas dégrader les 8 µm intrinsèques des données initiales, puisque cette fois on fait tout en double précision. Ou alors...

La condition d'un "triangle assez grand" devrait être facile à respecter: on peut par exemple partir de triangulations conçues pour les calculs d'éléments finis. Par contre, dès qu'on fait une opération de compensation sur la pièce, on intersecte sa surface par une autre surface. Et à ce moment CGAL commence à se rendre utile. En effet, au niveau le plus élémentaire d'un quelconque algorithme géométrique, on finira bien par intersecter un segment 3D avec un plan. Selon que les surfaces sont rasantes ou non (et elle le sont toujours à un certain endroit, ne serait-ce que par continuité), déterminer si un des deux points du segment est au-dessus ou au-dessous du plan est très difficile (c'est là que nous utilisons l’algorithme de Shewchuk par exemple).

Si la raison n'en est pas évidente, pensez au simple fait qu'un demi-bit est obligatoirement perdu lors d'une soustraction ou addition. Lors du calcul d'une normale sur 3 points sur une certaine "grille de précision" (celle de la représentation des points), on va générer une surface bien plus précise que celle de la grille des points servant au calcul, c'est à dire non représentable dans le même codage informatique (un peu comme si vous coupiez un cube de legos en diagonale: la coupe ne passe pas par les limites entre morceaux. Exemple, pages 5 et 6). Comme chacune des soustractions (et il y en a pas mal dans le calcul d'une normale) dégrade la qualité du résultat, le simple ordre dans lequel est fait le calcul change la normale, et donc le résultat de la question de savoir si un point est au-dessus ou au-dessous du plan considéré. Encore une fois ceci n'est pas évitable par l'utilisation de la double précision: il suffit de faire une itération (par exemple continuer l’algorithme avec le résultat de l'intersection plan / segment) pour voir que le problème se compose à l'infini: à chaque étape on doit augmenter la précision, même si au final on cherche un résultat sur 1 bit (vrai ou faux). On est bien dans la problématique de l'explosion combinatoire, et non pas dans un problème de taille de représentation.

Une fois que deux triangles s'intersectent, on peut dire adieu à toute contrainte de taille minimale, et le problème du calcul de la normale revient décuplé: on peut très bien complètement inverser une normale en déplaçant un point de 8 µm. On peut aussi "fermer" un triangle en confondant deux points après déplacement, s'ils sont éloignés de par exemple 1 µm (ceci n'est pas évitable dès qu'on applique un algorithme quelconque). Dans ces cas des propriétés géométriques (cette face est-elle visible de tel point?) voire topologiques (y a-t-il des triangles dégénérés sur 2 points?) sont perdues.

Cela n'est pas évitable en augmentant la taille de la représentation, y compris bien au-delà de 80 bits. En effet, imaginez 2 segments 2D codables sur 4 bits (0,0)-(14,1) et (0,1)-(15,0). Leur intersection nécessite une représentation plus grande que les données initiales: au point d'intersection, x vaut (14*15)/29, impossible à représenter sur 4 bits. Si l'algorithme est itératif, ce résultat va être utilisé, et au bout d'un moment, on dépasse toute taille de représentation normale. Diviser la taille de l'univers par la taille d'un atome ne change rien: la réponse mathématique nécessite bien une précision supérieure (au passage, quand CGAL parle de 1e-380, ce n'est pas une allusion à la représentation en double précision: on vient de voir que l'intersection nécessite de rajouter plusieurs dizaines de bits selon l'angle, donc une distance à une droite de 1e-380 imposerait des calculs ne tenant pas en double précision. Ils aurait pu mettre 1e-780).

Est-ce utile? Dans la quasi totalité des cas, non, comme je l'indiquais dans mon post initial. Sauf si on applique une correction d'outil sur un pli faux dans une surface, causé par une normale fausse de 80°, elle même causée par une erreur de 8 µm sur une position, elle-même causée par un triangle trop petit, causé par un point d'un mauvais coté d'un plan, causé par une intersection entre deux pièces tout à fait légitime et cette fois macroscopique (par exemple au centième de mm). On se retrouve avec une broche de 40 mm faisant un beau trou dans un fuselage, pour des problèmes de calcul mettant en jeu une précision capable de positionner exactement un atome dans l'univers.

Je ne peux trouver meilleur résumé que la citation de CGAL indiquée dans mon premier post: il s'agit d'un problème COMBINATOIRE, et non pas NUMERIQUE.

Par contre, mes compétences didactiques s'arrêtent à peu près à ce post: pour aller plus loin il faut lire les lien ci-dessus attentivement. J'ai trop les mains dans le cambouis pour ces problèmes de précision depuis des décennies, ils me sont donc tout à fait évidents maintenant. Mais je me souviens des années 85-90, où on ne disposait pas de la connaissance actuelle, et où on pensait que CATIA et autres devaient bien avoir résolu tout ça, avec des epsilons malins et tout... On en a vu des trous dans des fuselages, et on ne comprenait pas bien pourquoi, du moins au niveau du bureau d'étude, même si des universitaires étaient déjà sur le coup. Je pense que maintenant c'est un domaine bien balisé, surtout depuis le milieu des années 90.

[souviron34]

Je m'excuse mais je ne suis toujours pas convaincu (et même plus vous avancez plus vous me convainquez du bien-fondé de ma position)...

Par exemple pour les pièces avion, elles sont usinées. L'usinage passe toujours par une phase de compensation d'outil, qui va s'appuyer sur la géométrie connue par la machine d'usinage.

OK.

Mais un usinage se fait au maximum au micron.. Donc e-6 donc 6 chiffres. Si on prend par rapport à l'avions, disons 100 m (je suis large ) cela fait 8 chiffres significatifs...

Nous sommes toujours dans les limites normales..



Je pense que le problème vient soit du fait du format de passage, soit de l'algorithme utilsé.. (et sans doute du processus utilsé pour communiquer)..


Mais franchement, mathématiquement ET informatiquement, vous ne me convainquez absolument pas..


Admettons que l'on représente des pièces au micron sur des longueurs de 100m. Admettons que l'on souhaite avoir une intersection.

La précision d'usinage étant au micron, il faut descendre un cran en dessous pour pouvoir faire un arrondi correct.

Nous sommes donc à 9 chiffres significatifs...

Rien de ceci n'est infaisable avec simplement des nombres en doule (voire simple) précision...


Je suis toujours perplexe, et les explications CGAL ne m'éclairent pas plus...


Il est étrange que l'on ait pu envoyer et calculer les orbites de Voyager autour de Jupiter ou Saturne sans avoir de machines 80 bits et tourner sur des e380 de précision


Mon esprit et ma formation de physicien crie au scandale et à l'imposture quand on me dit que pour évaluer des ordres de grandeurs de 10-8 on a besoin quasiment d'une infinité...... (et même ne serait-ce que de 80 bits)...

Déjà 64 permettent de représenter e308...

[ac_wingless]

euh... 10 µm d'erreur sur une coordonnée avion, c'est pas grave, mais une normale qui bascule de 70° parce qu'on bouge un point de 10 µm, c'est grave potentiellement, selon l’algorithme considéré. Je sais pas comment le dire plus clairement!
Je peux vous retourner le commentaire que vous adressiez à Ben.oeilnoir: si les douzaines de scientifiques contribuant à CGAL s'embêtent à avoir fait 700k lignes de librairie sur plus d'une décennie pour rien, ça serait sympa de leur expliquer

[souviron34]

Je peux vous retourner le commentaire que vous adressiez à Ben.oeilnoir: si les douzaines de scientifiques contribuant à CGAL s'embêtent à avoir fait 700k lignes de librairie sur plus d'une décennie pour rien, ça serait sympa de leur expliquer

normal, je l'ai cherché

mais voir plus bas...



Mais quand même, ce que j'ai rajouté plus haut et qui est passé en douce :

Mon esprit et ma formation de physicien crie au scandale et à l'imposture quand on me dit que pour évaluer des ordres de grandeurs de 10-8 on a besoin quasiment d'une infinité...... (et même ne serait-ce que de 80 bits)...

Déjà 64 permettent de représenter e308...

Je le répète, cela me semble comme les biblothèques des grands nombres, utiles seulement pour la cryptographie...

Je n'ai rien contre les gens de CGAL, mais je pense que par rapport à votre type de problème mon esprit de physicien s'insurge..

Il doit y avoir un problème dans la conception du calcul pour qu'on doive utiliser ce genre de choses..

Je rapprocherais un peu ça des expériences sur la réforme de l'enseignement. Auant été elvé aux maths classiques, je me suis retrouvé étudiant à donner des cours de physique à des Terminales C ayant eu des maths modernes.

Ne sachant pas ce qu'était un ordre de grandeur, ils étaient perdus et trouvaient des solutions farfelues..

Je ne dis pas que CGAL ait fait (ou fasse) quelque chose d'inutile.
Je dis qu'il est IMPENSABLE (impossible physiquement) d'avoir besoin de e10 précison de plus que la précision demandée..

Quand dans mon domaine d'origine on calcule la focale d'un télescope, elle est du micron à 12 mètres.. Et ? aucun organisme n'a eu besoin de calculateurs à 80 bits ou de super-biblothèques pour les fabriquer..

Franchement, je pense que c'est plus la manière de faire (l'algorithme) qui nécessite cela que la réalité physique..

En effet admettons qu'une facette à un bout de l'avion nécessite qu'à l''autre bout on ait une précision de 1 micron sur sa normale : dans ce cas-là on atteint bien e-15 de préciion demandée.

Cependant c'est totalement faux dans la pratique : n'importe quelle bosse même en bout de fuselage n'influence en rien (surtout si elle est de l'ordre du micron) ce qui se passe de l'autre côté du fuselage..


Je crois que ce sont les programmes de maillage qui forment un seul modèle du tout qui pourrait décaler.. Mais c'est donc un problème d'algorithme et de propagation des erreurs et non pas un problème de géométrie et d'intersection (et c'est en ça que je dis que mon fond de physicien se révolte).


Ceci étant dit

je m'en fiche un peu, je voulais juste insister sur le fait que l'intervention de ben.oeilnoir était déplacée, surtout en disant "ne marche pas dans 100% des cas"..

Pour exemple : quand j'ai travaillé pour la météo, j'avais par exemples des impacts d'éclairs dont la précision était de e-5 en lat-lon. Transformés en coordonnées rectangulaires (en double), l'échelle était de e+6 avec une précision utilsable de e-7. TOUTES les intersections calculées grâce à la formule sont correctes, donnat une précision relative de e-13... dans une intersection...

[ac_wingless]

Vous avez tout à fait raison quand vous dites qu'aucune grandeur physique ne mérite la double précision, voire la simple. N'importe quelle bosse ou éraflure pulvériserait ces précautions. Tant que les formules les plus compliquées sont calculées avec 80 bits, il est rarissime d'avoir des soucis. Cela arrive parfois (rappelez vous vos calculs d'erreurs sur les dénominateurs), mais ce n'est pas à cette classe de problème que s'attaque CGAL et la géométrie algorithmique. D'autres méthodes sont bien plus adaptées (intervalles de confiance, ordre des calculs, etc).

Par contre, aucune imprécision n'est tolérable sur certains résultats logiques utilisés en algorithmie, et ce à une précision qui peut en théorie devenir presque infinie. Si on se trompe, on ne se trompe pas d'une fraction d'angström, on se trompe carrément de coté pour faire l'usinage. Ou bien on croit qu'il y a de la matière dans un endroit vide, et inversement. On pense que l'outil peut prendre ce chemin, alors qu'on fait une collision énorme. Etc. C'est la différence essentielle avec les cas que vous citez.

La manière dont une simple erreur numériquement négligeable peut s'escalader à ces niveaux dépend de l'algorithme. J'ai cité par exemple les compensations d'outil qui se basent sur une direction de normale pour décaler l'outil, parce qu'il est simple à comprendre (bien que faux: on utilise d'autres méthodes pour déterminer les chemins d'usinage, en partie à cause de ces problèmes). Une erreur de 25° créerait des pièces fausses, une erreur de 135° casserait la machine. Comment peut-on se planter de 90° (macroscopique) si tous les calculs sont précis au micron (microscopique)? Parce que se tromper de quelques microns sur un sommet d'un triangle de quelques microns randomise sa normale, et qu'interdire des triangles trop petits est impossible si l'objet décrit est le résultat d'une intersection de surface.
Bien d'autres algorithmes se comportent de cette manière: soit on est exact, soit on ne l'est pas, et si on ne l'est pas, on part dans la choucroute totale.

La beauté de CGAL par rapport aux premières méthodes des années 80 (basées sur des librairies à grand nombres et sur les mathématiques dites "paresseuses") est qu'on ne paie que quand le problème arrive. Dans la plupart des cas, utiliser une précision parfaite n'impose qu'un surcout de 25%, ce qui indirectement confirme ce que vous dites: le problème aigu ne se produit que rarement. Selon les applications, le surcout peut aller à 80%, voire beaucoup plus d'après ce qu'ils disent. Je n'ai jamais constaté cela.

Par contre, j'ai constaté à de nombreuses reprises que ne pas utiliser les méthodes exactes avait des conséquences macroscopiques: certains meshs passent très bien, d'autres perdent la moitié de leur volume! Si vous reprenez l'exemple du segment codé en 4 bits ci-dessus, et que vous iterez un algorithme cela devient clair: le résultat n'étant pas codable sur 4 bits, il faut soit augmenter la précision à chaque étape de calcul, soit "snapper" les points sur la précision d'entrée. C'est en général possible, sauf dans les cas limite (ceci dépendant de l'algorithme et de ce qu'on souhaite tester). C'est exactement de cette manière que CGAL contient l'explosion combinatoire: retomber à chaque étape sur la représentation la plus petite permettant de ne pas compromettre l'exactitude du résultat recherché.

[souviron34]

désolé de répondre si tard, j'avais un problème d'Internet...


J'admet parfaitement sur la théorie.. puisque "parfait" n'existe pas...

Néanmoins (et en corrigeant un facteur 10 malencontreusement inclus dans mon post précédent), je noterais :

tolérance sur un angle = 1 micron à 100 m = 10-14 (10-6 / 10+8)

Admettons un cas un peu plus réaliste (quoique) dans la fabrication :

tolérance d'angle = 1 micron à 1 m = 10-12 (10-6 / 10+6)

Déjà sans changer de repère les double suffisent si il y a au max 5 opérations (puisque la limite de précision d'un double en 32 bits est de 10-13 à 10-15)


Mas il suffit de se mettre en mm pour se ramener à 10-6... (10-3 / 10+3)

Il faudrait alors pour chaque point plus de 0.5 10+8 calculs pour avoir besoin d'une précision supérieure à celle donnée par les doubles...


Avoir 1/2 milliard d'opérations par point est vraisemblablement innateignable dans tous les modèles de meshs quels qu'ils soient..


Donc le problème de précision est absurde... pour des calculs tels que ceux mentionnés...




Comme mentionné plus haut, ce problème vient donc d'une mauvaise approche du problème (pas la bonne échelle) plutôt que d'une précision demandée par les calculs...


Pour en revenir au sujet, je ré-itère que la formule donnée est simultanément géométriquement exacte et numériquement exacte pour tous les cas de figures, si on a choisi une échelle correspondant aux données traitées...

[souviron34]

@ac_wingless :

t'ai-je convaincu ?


Pour pousser le bouchon un peu plus loin :


Soit une tolérance exigée de 0.1 micron à 100 m :

Si l'unité est le mm, alors cela fait 10-4/10+5 = 10-9

Il faudrait donc plus de 5000 opérations par point pour avoir besoin d'autre chose que des double-précisions 32 bits et garantir ce critère... (précision max d'un double 32 bits 10-13)

[ac_wingless]

Ma foi j'avais plutôt laissé tomber... Vous ne semblez pas lire mes posts (vous ressortez systématiquement le même exemple de précision de représentation, ignorant qu'une bête division peut aller jusqu'à doubler la taille de la représentation nécessaire au stockage du résultat, ce qui met en évidence l'aspect combinatoire et non pas numérique du problème). Et puis, j'ai parfois du mal avec vos exemples, peut être tapés un peu trop vite... "1 micron à 1m" c'est 1e-6, et pas 1e-12, la limite de précision d'un "double" (qui n'est pas sur 32 bits, mais 64) est meilleure que 1e-13: on a 53 bits de mantisse utiles (1 bit est implicitement à 1), soit une résolution de 1.1e-16 à l'intérieur d'une plage définie par l'exposant courant, donc encore plus précise en superposant les jeux de valeurs en provenance de plusieurs exposants contigus). Quant aux 5000 ou demi milliard d'opérations, je n'ai pas d'idée comment vous y arrivez, mais le résultat part en vrille bien avant (voir ci-dessous).

Mais le plus bloquant dans cette discussion qui n'avance pas du tout est que ce qui est représentable par un nombre fixe de bits est de toute façon complètement hors sujet: à partir du moment où une décision macroscopique (par exemple logique) peut être faussée sur un arrondi, on sort des problèmes numériques pour rentrer dans les problèmes combinatoires. En effet, la classe de problème qu'adresse CGAL et consorts n'a aucun rapport avec la précision d'un nombre, mais concerne la précision requise pour assurer l'exactitude d'une décision prise d'après le résultat d'une série d'opérations. Vos exemples sur les angles sont révélateurs de cette confusion: vous parlez (encore!) de représentation sous forme informatique de la valeur numérique d'un angle, alors que l'exemple consiste à assurer l'exactitude d'une décision, comme le coté où mettre une broche, qui peut demander une précision plus ou moins dure que le micro-radiant (mais en tout cas sans rapport avec ce qu'un µradiant représente réellement; on parle d'une broche de 15 tonnes, qui devrait se trouver là, ou bien 5 mètres plus loin: c'est ça la vraie question), sur la normale d'un triangle de taille de l'ordre du µm, dans le cas où un sommet peut être faussé, par une simple addition causée par le passage en coordonnées avion, de 8 µm. Quand vous dites que "ce problème vient donc d'une mauvaise approche du problème (pas la bonne échelle) plutôt que d'une précision demandée par les calculs", c'est que vous ne voyez tout simplement pas que c'est le problème: la précision est bel et bien demandée par les calculs, pas par le stockage du résultat sur lequel vous vous focalisez. On s'en fiche un peu (en fait, beaucoup) de la taille de la représentation des entrées ou des sorties ou de connaitre la normale d'une face au microradiant près. Par contre si la broche passe au travers de la pièce, ça gène.

En conséquence, il est complètement inutile de parler de relation entre grandeur physique et représentation informatique, puisqu'il suffit d'itérer une opération, par exemple dans un algorithme, pour voir exploser tout espoir de stocker le résultat à l'intérieur de 64 bits: vous conviendrez que si on perd 1/2 bit par opération sur deux nombres lorsqu'on stocke le résultat sous la représentation informatique servant aux opérandes, on ne peut pas le faire une douzaine de fois sans conséquence, et encore moins un demi milliard de fois. Par contre, le demi bit de précision perdu en théorie n'est pas toujours significatif du point de vue de la décision en cours d'évaluation. Autrefois (fin des années 80), on assurait l'exactitude de cette décision en assurant une précision à coup sûr, c'est à dire en expansant systématiquement la représentation numérique nécessaire à l'exactitude. Aujourd'hui, on ne paie la précision supplémentaire que lorsqu'elle est utile. Pour des raisons de performance, adaptativement et en fonction de la question posée (c'est très important), on reste si possible dans la précision des opérandes ... ou pas du tout! Selon la question posée, on peut très bien rester sur 64 bits tout du long, ou avoir besoin de 53822 bits à un certain moment du calcul. Et ce avec les mêmes données d'entrée, mais deux questions différentes!

Je me suis fatigué à trouver un exemple ultra-simple, sur quelques bits (bien entendu, travailler sur plus de bits ne change rien à l'exemple, il vous suffit de ne prendre que les bits de poids faible des mantisses considérées), dépourvu de toute notion physique pour vous éviter de recourir une nouvelle fois à des évaluations de la précision nécessaire à la représentation de la valeur physique considérée, et qui montre en direct la fameuse "explosion combinatoire" à laquelle fait référence l'introduction de CGAL. J'avoue que là, si le message ne passe pas, j'abandonne définitivement , et je vous renvoie aux arguments d'autorité des experts, fort nombreux dans les liens ci-dessus.

Donc voilà la question: soit A l'intersection des segments (0,0)-(14,1) et (1,0)-(15,0), et B celle des segments (4,0)-(9,1) et (4,1)-(12,0). Le point (3,3) est il du même coté de la droite AB que l'origine?
Les données de l'exposé tiennent sur 4 bits. Le résultat tient sur 1 bit. Les calculs intermédiaires non optimisés requièrent un tout petit peu moins de 25 bits, et les calculs strictement minimaux ad hoc impossibles à généraliser nécessitent un petit peu moins de 10 bits (je vous laisse les effectuer). Dans tous les cas, on a besoin de PLUS de 4 bits pour stocker les résultats intermédiaires, il suffit donc d'itérer UNE fois pour se prendre une imprécision macroscopique: si vous devez stocker A et B dans la représentation des données d'entrée, l'inclinaison de la droite AB est limitée aux 8 angles possibles puisque A et B sont dans la même "case" de la grille correspondant à la résolution de la représentation. Comme la droite AB est inclinée à environ -30°, on a au mieux 15° d'erreur sur des données sur 4 bits, en une seule itération.

J'espère que ça vous convaincra. Sinon, vous devriez soit faire confiance aux spécialistes (voir les nombreux liens ici), par exemple après les avoir lu attentivement, soit débattre avec eux directement.

[souviron34]

oh !!!

Pas la peine de s'énerver !!!

Je lis et je ne comprend pas...


Maintenant merci de ce long post, je vais regarder à tête reposée, ainsi que le lien...

Mais j'avoue avoir toujours du mal à comprendre pour l'instant..

"1 micron à 1m" c'est 1e-6, et pas 1e-12,

Non, si l'unité est le micron, pour avoir 1 micron de précision (orthogonale) à 1 mètre de distance il faut bien 10-12, c'est à dire 1 micron / 1 million de micron (théorème de Pythagore)..

(puisqu'on parlait de normales et d'angles : je dis "normales confondues si point d'impact à 1m à l'intérieur du même micron")

la limite de précision d'un "double" (qui n'est pas sur 32 bits, mais 64) est meilleure que 1e-13:

Je sais bien que c'est sur 64, puisique c'est double-précision..

Oui c'est exact c'est meilleur, mais si je prend les fichiers systèmes :

http://en.wikipedia.org/wiki/Machine_epsilon

DBL_ESPILON 1.11e-16

mais ça ne change pas le problème de fond..

Quant aux 5000 ou demi milliard d'opérations, je n'ai pas d'idée comment vous y arrivez

Très simple : on perd 0.5 à chaque arrondi.. (même si je me suis trompé d'une puissance de 10, ça reste quand même très élevé)

Pour avoir une précision de 10-9 à la fin, il faut avoir fait une opération avec 2 nombres à 10-10. Chacun de ces nombres peut être issu d'une opération à 10-11. Et ainsi de suite. Ce qui donne 2^4 = 64 opérations entre 10-9 et 10-13, 128 à 10-14, etc...

Maintenant, si on additionne 2 nombres à 10-14, on a un nombre à 10-13. Pour basculer de 5 10-13, il faut 5 opérations à 10-14. Et ainsi de suite...

Pour avoir 5 10-10 (donc une précision de 10-9) il faut 1000 opérations basculant de 5 10-13, donc 5000 opérations à 10-14






Je vais tenter de me pencher sur le problème, mais j'avoue ne pas voir à l'heure actuelle la différence que vous faites entre mon point de vue et :

à partir du moment où une décision macroscopique (par exemple logique) peut être faussée sur un arrondi, on sort des problèmes numériques pour rentrer dans les problèmes combinatoires. En effet, la classe de problème qu'adresse CGAL et consorts n'a aucun rapport avec la précision d'un nombre, mais concerne la précision requise pour assurer l'exactitude d'une décision prise d'après le résultat d'une série d'opérations. Vos exemples sur les angles sont révélateurs de cette confusion: vous parlez (encore!) de représentation sous forme informatique de la valeur numérique d'un angle, alors que l'exemple consiste à assurer l'exactitude d'une décision, comme le coté où mettre une broche, qui peut demander une précision plus ou moins dure que le micro-radiant (mais en tout cas sans rapport avec ce qu'un µradiant représente réellement; on parle d'une broche de 15 tonnes, qui devrait se trouver là, ou bien 5 mètres plus loin: c'est ça la vraie question), sur la normale d'un triangle de taille de l'ordre du µm, dans le cas où un sommet peut être faussé, par une simple addition causée par le passage en coordonnées avion, de 8 µm. Quand vous dites que "ce problème vient donc d'une mauvaise approche du problème (pas la bonne échelle) plutôt que d'une précision demandée par les calculs", c'est que vous ne voyez tout simplement pas que c'est le problème: la précision est bel et bien demandée par les calculs, pas par le stockage du résultat sur lequel vous vous focalisez. On s'en fiche un peu (en fait, beaucoup) de la taille de la représentation des entrées ou des sorties ou de connaitre la normale d'une face au microradiant près. Par contre si la broche passe au travers de la pièce, ça gène