Partage
  • Partager sur Facebook
  • Partager sur Twitter

Opérations sur les nombres flottants

Approximation des réels mathématiques ?

    7 mai 2009 à 18:38:28

    Je crée ce topic suite au gros hors-sujet qui a commencé environ ici, suite à une erreur de ma part.

    Si des gens s'intéressent vraiment au sujet (moi pas), ou s'ils découvrent et sont curieux, je les invite la page wikipédia à ce sujet pour commencer.


    Citation : Cacophrene

    Salut !

    Citation : bluestorm

    Par ailleurs, Cacophrène, tes histoires de "sous-ensemble de ..." ne sont pas très convaincantes puisque les opérations sur les flottants ne sont pas les opérations usuelles dans R (typiquement 0.1 + 0.2 ne fait pas 0.3).


    Ce ne sont pas « mes histoires ». Il suffit de travailler à epsilon_float près (plus simplement encore : arrondir à un certain nombre de décimales) pour éviter les erreurs d'arrondis et autres joyeusetés liées à la représentation interne des flottants. Moyennant cette précaution, on retombe peu ou prou sur les opérations dans R. Je maintiens que l'approximation n'est pas si mauvaise que ça.

    Toutefois, si réserve il y a, elle concerne plutôt le fait que ce n'est pas du tout R mais bel et bien Q dont les flottants sont un sous-ensemble approximatif. Aucun nombre irrationnel ne peut être représenté correctement par un flottant. Mais là encore l'erreur d'approximation est-elle si importante qu'elle fasse rejeter l'analogie sans hésiter ? Je ne le crois pas.

    Citation : bluestorm

    Effectivement, c'est un sujet vachement pas drôle. Encore plus sordide que les histoires d'overflow.


    Sordide ou pas, c'est un point crucial dans la mesure où beaucoup de débutants sont tentés de faire des boucles avec des tests d'égalité sur les flottants comme condition d'arrêt (et aucune raison évidente ne peut leur révéler le risque que cela comporte). Cec dit, je suis bien d'accord pour dire qu'il est déplaisant d'être sans cesse rappelé à la dure réalité de la "représentation interne qui fait ceci quand je pense qu'elle fait cela". Sans parler des optimisations que tu évoques, qui compliquent encore la chose... :p

    Cordialement,
    Cacophrène



    L'approximation a ses mérites, puisqu'elle nous permet de penser les opérations flottantes en termes d'opérations sur les réels qui nous sont familières (ou pas). Mais dès qu'on s'intéresse aux problèmes liés justement à la représentation des flottants, elle cesse d'être pertinente, justement parce que la partie qu'on essaie de comprendre est celle qui est "effacée" par l'approximation.

    C'est comme si on disait "l'hypothèse selon laquelle la terre est plate est bien pratique pour faire des cartes des pays, donc ce n'est pas une si mauvaise approximation que ça". C'est très vrai, mais si tu l'expliques à un gars qui prépare un tour du monde en ballon, il va trouver que tu es un peu à côté de la plaque : dans son cas, ton approximation n'a pas grande valeur.

    Sinon, pour continuer dans les relatives banalités, ce n'est même pas un sous-ensemble de Q, puisque les fractions dont les facteurs premiers du dénominateur ne sont pas 2 ne sont pas représentables : 0.2 donne lieu en base 2 à un développement décimal infini, qui est donc tronqué par la représentation mémoire. On pourrait donc approximer cela à l'ensemble des sommes de puissances de 2 (puissances positives et négatives, dans un certain intervalle qui dépend de la précision, pour les très grands et les très petits nombre, de la représentation des flottants). Je ne connais pas très bien le sujet mais il me semble qu'il y a en fait d'autres subtilités, comme l'existence de "classes" distinctes (cf. la documentation caml à ce sujet) qui marchent bien en pratique mais rendent la formalisation des opérations flottantes assez peu ragoûtantes.
    • Partager sur Facebook
    • Partager sur Twitter
      7 mai 2009 à 19:55:05

      Salut !

      Citation : bluestorm

      L'approximation a ses mérites, puisqu'elle nous permet de penser les opérations flottantes en termes d'opérations sur les réels qui nous sont familières (ou pas). Mais dès qu'on s'intéresse aux problèmes liés justement à la représentation des flottants, elle cesse d'être pertinente, justement parce que la partie qu'on essaie de comprendre est celle qui est "effacée" par l'approximation.


      L'approximation est intéressante tant qu'elle est valable. Or on choisit une approximation parce qu'elle est intéressante dans un contexte où elle est valable. Pléonasme ?

      Citation : bluestorm

      C'est comme si on disait "l'hypothèse selon laquelle la terre est plate est bien pratique pour faire des cartes des pays, donc ce n'est pas une si mauvaise approximation que ça". C'est très vrai, mais si tu l'expliques à un gars qui prépare un tour du monde en ballon, il va trouver que tu es un peu à côté de la plaque : dans son cas, ton approximation n'a pas grande valeur.


      Hé hé hé même pour les pays d'ailleurs ^^ je doute que ça marche bien pour la Russie qui, dans ses frontières actuelles, compte 11 fuseaux horaires. :)

      Citation : bluestorm

      On pourrait donc approximer cela à l'ensemble des sommes de puissances de 2 (puissances positives et négatives, dans un certain intervalle qui dépend de la précision, pour les très grands et les très petits nombre, de la représentation des flottants). Je ne connais pas très bien le sujet mais il me semble qu'il y a en fait d'autres subtilités, comme l'existence de "classes" distinctes (cf. la documentation caml à ce sujet) qui marchent bien en pratique mais rendent la formalisation des opérations flottantes assez peu ragoûtantes.


      Voui, c'est un monde à part entière. Il y a des références intéressantes sur caml et l'arithmétique rationnelle exacte par Valérie Ménissier-Morain sur le net. Faudrait que je retrouve quelques liens (Google le fait sans doute très bien).

      Cordialement,
      Cacophrène

      PS : Je suis navré que le fil de discussion consacré au « P'tit langage » ait ainsi dérivé sur une problématique très différente de l'idée de départ, en partie par ma faute.
      • Partager sur Facebook
      • Partager sur Twitter
        7 mai 2009 à 20:08:23

        Boarf écoute, si ça intéresse les gens c'est comme ça, on va pas perdre de temps à se jeter des cailloux. On aurait dû penser à forker le topic avant (à quand une fonctionnalité pour forker des topics en emportant une partie des messages ?), mais on va pas critiquer les gens qui parlent de ce qui les intéresse.
        • Partager sur Facebook
        • Partager sur Twitter
          7 mai 2009 à 20:55:48

          De toute façon, poster cite fait un truc hs, c'est plus rapide que coder un interpréteur de Lisp, on n'y peut rien.

          Pour les fuseaux horaires, c'est pas directement lié à la rotondité ( :-° ) de la terre.

          Sinon, est-ce que ça serait jouable de représenter les _réels_ par des suites de rationnels dont ils seraient la limite ?
          Vu qu'un rationnel, ça se représente facilement, on aurait une représentation exacte des réels, après pour les opérations on les traduit en termes de suites.

          J'avais essayé de faire ça une fois, mais le problème c'est que pour des précisions très faibles, la fonction mettait 30 ans (c'était
          _____                 
          \        1          
           \      ---              
           /       n !              
          /____
          pour le nombre e)


          Vu que c'était pas ma seule préoccupation, j'ai laissé tomber assez vite, mais je me demandais si en trouvant d'autres fonctions, ça serait possible ou pas.

          edit : galère sans connaître latex :-°
          • Partager sur Facebook
          • Partager sur Twitter
            8 mai 2009 à 0:10:25

            À ton service: <math>\(\sum \limits_{n=0}^{max} \frac{1}{n!}\)</math>

            \sum \limits_{n=0}^{max} \frac{1}{n!}
            
            • Partager sur Facebook
            • Partager sur Twitter
              8 mai 2009 à 0:22:07

              Maxibolt : il existe d'autres suites représentant e et qui convergent nettement plus vite.

              Oui, ta méthode est possible, et c'est même une des constructions possibles du corps des réels (celle de Cauchy).

              Le problème c'est que cette méthode reste limitée par les pouvoirs d'expression : tout réel peut être représenté par une suite de rationnels, mais ton ordinateur ne pourra travailler que sur les suites que tu lui donnes, donc qui sont "représentables" (qui sont issues de formules que l'on peut 'calculer' en quelque sorte). Il y en a en fait un nombre dénombrable (des formules de taille finie sur un alphabet fini), et quelle que soit ta méthode de représentation tu laisseras donc la plupart des réels sur le carreau.
              • Partager sur Facebook
              • Partager sur Twitter
                8 mai 2009 à 0:24:51

                l'avantage de la représentation en flottants (ou en virgule fixe) c'est qu'il ai aisé de faire des calculs dessus.

                Si tu utilises d'autre représentations, les calculs deviennent non triviaux ^^
                • Partager sur Facebook
                • Partager sur Twitter
                  4 avril 2010 à 16:14:50

                  Je m'excuse de déterrer le topic, d'autant que je ne comprends que difficilement les sujets qui y sont abordés.

                  Toutefois j'ai une question concernant la représentation des flottants en mémoire :
                  Pourquoi ne pas représenter les réels comme une fraction de deux entiers ? En admettant que la taille de ces entiers n'est limitée que par la mémoire de la machine, ce qui laisse de la marge, on pourrait ainsi représenter tous les nombres de <math>\(\mathbb{R}\)</math>, enfin je crois :euh: (pardonnez mon faible niveau en maths)

                  De plus les opérations sur les fractions sont simplissimes à implémenter, du moins pour l'addition, soustraction, multiplication, et division.
                  Donc voilà, je ne prétends pas débarquer en ayant trouvé une « super idée », j'aimerais simplement connaître les limites de cette méthode, savoir pourquoi elle n'est pas utilisée, etc…
                  Entraîne-t-elle des problèmes de performances ?

                  Merci d'avance :)
                  • Partager sur Facebook
                  • Partager sur Twitter
                  Administrateur du forum Paul Diel
                    4 avril 2010 à 19:49:49

                    Déjà, la première limite de cette méthode c'est qu'on ne peut pas représenter tous les nombres réels par un quotient de deux entiers (un exemple connu est la racine carrée de 2, cf http://fr.wikipedia.org/wiki/Racine_ca [...] ionalit.C3.A9 )
                    Ensuite, la taille du résultat peut beaucoup grandir avec le nombre d'opérations faites (parce qu'on fait des multiplications à chaque fois), donc ça finit par prendre beaucoup de place et avoir des mauvaises performances pour un gain de précision pas forcément utile.

                    Par contre, on peut approcher tous les nombres par des rationnels de façon aussi proche que l'on veut : on peut donc représenter exactement les réels par une suite d'approximation successives, et calculer jusqu'à ce qu'on obtienne la précision requise. Mais c'est encore une méthode qui peut demander beaucoup de temps de calcul.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      4 avril 2010 à 23:37:06

                      Merci de cette réponse.
                      Je ne savais pas que <math>\(\mathbb{Q}\)</math> était contenu dans <math>\(\mathbb{R}\)</math>.
                      J'aurais une autre question : comment fait une bibliothèque comme GMP pour représenter des flottants ? La précision est-elle infinie ?
                      • Partager sur Facebook
                      • Partager sur Twitter
                      Administrateur du forum Paul Diel
                        4 avril 2010 à 23:58:17

                        Citation : Babilomax

                        La précision est-elle infinie ?



                        Non, elle n'est a priori pas "infinie". Le fait que l'on calcule encore des décimales de <math>\(\pi\)</math> (on doit en être à deux ou trois mille milliards actuellement) montre bien que l'on a pas une précision infinie stricto sensu, puisqu'il existe des nombres (dont <math>\(\pi\)</math> fait partie) dont l'on ne pourra jamais écrire le développement décimal entier.

                        D'un autre côté, comme te le dira wikipedia, il te suffit de connaître juste les 39 premières décimales de <math>\(\pi\)</math> pour calculer la circonférence d'un cercle de la taille de l'ordre de celle l'univers avec une précision inférieure au diamètre d'un atome d'hydrogène, donc avoir deux mille millards de décimales n'est pas forcément utile pour mener des calculs qui restent raisonnablement précis - tout dépend de ce que tu cherches.

                        Ultimement, une forme de précision infinie peut être atteinte en faisant du calcul formel, c'est à dire du calcul d'expressions mathématiques plutôt que de flottants, comme le font Maple ou Mathematica - ce qui revient en somme à manipuler les nombres sans les calculer, uniquement en se servant de relations et de propriétés connues à leur propos. Mais l'on retrouve les problèmes de précision dès que l'on veut évaluer numériquement (id est calculer sous forme de flottants) ces nombres-là...
                        • Partager sur Facebook
                        • Partager sur Twitter
                          5 avril 2010 à 21:37:07

                          Et si on ne compte pas représenter des irrationnels ?

                          En fait, je serais intéressé par une précision infinie car je voudrais m'exercer en créant une bibliothèque de géométrie euclidienne (dans l'espace et dans le plan).
                          Or une précision infinie serait fort utile pour les calculs d'intersection et de « contenance » des éléments euclidiens (géométrie analytique). De plus, ce genre de calculs ne fera (presque) pas intervenir de nombres irrationnels.

                          J'aimerais donc savoir si cette représentation est adaptée, sachant que les performances sont primordiales.
                          Merci de votre aide.
                          • Partager sur Facebook
                          • Partager sur Twitter
                          Administrateur du forum Paul Diel
                            5 avril 2010 à 22:00:35

                            Si tu veux des calculs exacts, pourquoi ne pas conserver les expressions symboliques ? J'ai l'impression que tant que tu as des nombres algébriques, des calculs symboliques suffisent et sont relativement performants.
                            • Partager sur Facebook
                            • Partager sur Twitter
                              6 avril 2010 à 14:32:00

                              Si je comprends bien, avec du calcul symbolique je peux déterminer sans risques d'erreur si deux droites sont sécantes, mais je ne pourrais avoir qu'une valeur approchée du point d'intersection, c'est ça ?
                              • Partager sur Facebook
                              • Partager sur Twitter
                              Administrateur du forum Paul Diel
                                6 avril 2010 à 15:57:45

                                Il me semble (attention, je parle seulement selon mon intuition) que tu peux avoir une "valeur exacte", c'est à dire une expression symbolique du point d'intersection, en résolvant l'équation d'intersection des droites (ou de toute figure géométrique déterminée implicitement par des équations polynomiales).

                                Si on demande un développement décimal, tu es alors obligé de fournir une valeur approchée dès que le nombre est irrationnel, mais ça ne veut pas dire que l'expression symbolique n'est pas exacte.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  6 avril 2010 à 18:51:55

                                  Exemple simple :
                                  ma calculatrice, si j'entre <math>\(\mathrm{solve}(x = 1 - \sqrt{x}, x)\)</math>, me dit : <math>\(x = \frac{-(\sqrt{5} - 3)}{2}\)</math> (qui aurait pu cependant être simplifié en <math>\(x = \frac{3 - \sqrt{5}}{2}\)</math>), ce qui est bien une valeur exacte.
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                  Anonyme
                                    6 avril 2010 à 19:16:42

                                    Citation : spider-mario

                                    Exemple simple :
                                    ma calculatrice, si j'entre <math>\(\mathrm{solve}(x = 1 - \sqrt{x}, x)\)</math>, me dit : <math>\(x = \frac{-(\sqrt{5} - 3)}{2}\)</math> (qui aurait pu cependant être simplifié en <math>\(x = \frac{3 - \sqrt{5}}{2}\)</math>), ce qui est bien une valeur exacte.



                                    Un exemple encore plus simple :
                                    <math>\(sin(x)=0 \Longleftrightarrow x = \frac{\pi}{2}[\pi]\)</math>

                                    Donc oui il peut y avoir une valeur exacte mais pas de valeur qui puisse s'écrire sous la forme d'un nombre décimal. Après tout dépend ce que l'on cherche mais il faut savoir que dans les programmes usuels rien que le fait de compiler (en C, Fortran ou autre...) avec le flag -O3 fait perdre en précision de calculs.
                                    Donc la bibliothèque de géométrie ne pourra jamais être exacte mais pourra être précise... Je crois qu'on peut atteindre du <math>\(10^{-21}\)</math> assez facilement. Après il faut utiliser des algorithmes correctifs, j'en ai vu dans certaines publications de mathématiques mais c'est plus facile à lire avec un niveau doctorat et en anglais.
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      7 avril 2010 à 0:01:45

                                      Citation

                                      Après tout dépend ce que l'on cherche mais il faut savoir que dans les programmes usuels rien que le fait de compiler (en C, Fortran ou autre...) avec le flag -O3 fait perdre en précision de calculs.

                                      Euh, seulement si on effectue des opérations sur les nombres flottants. Si on fait du calcul symbolique, pas de problème.

                                      Du reste, ton exemple me semble un peu dangereux parce que justement <math>\(\pi\)</math> n'est pas un nombre algébrique; il n'est pas forcément évident de le comparer à d'autres nombres, et je ne suis pas sûr que la comparaison soit toujours décidable. En tout cas, l'algorithme le plus direct (calculer la série entière dont il est la racine, et vérifier que ça n'est pas nul) termine pour les nombres différents de pi (il répond "non" en un temps fini), mais pas pour pi (il ne répond pas du tout et boucle infiniment, au lieu de répondre "oui").
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Anonyme
                                        7 avril 2010 à 10:07:35

                                        Citation : bluestorm

                                        Citation

                                        Après tout dépend ce que l'on cherche mais il faut savoir que dans les programmes usuels rien que le fait de compiler (en C, Fortran ou autre...) avec le flag -O3 fait perdre en précision de calculs.

                                        Euh, seulement si on effectue des opérations sur les nombres flottants. Si on fait du calcul symbolique, pas de problème.

                                        Du reste, ton exemple me semble un peu dangereux parce que justement <math>\(\pi\)</math> n'est pas un nombre algébrique; il n'est pas forcément évident de le comparer à d'autres nombres, et je ne suis pas sûr que la comparaison soit toujours décidable. En tout cas, l'algorithme le plus direct (calculer la série entière dont il est la racine, et vérifier que ça n'est pas nul) termine pour les nombres différents de pi (il répond "non" en un temps fini), mais pas pour pi (il ne répond pas du tout et boucle infiniment, au lieu de répondre "oui").



                                        Je suis d'accord avec cela mais vu l'objectif du post qui est de faire une bibliothéque de géométrie pi est un élément indispensable et quand on voit les différentes représentations... Après tout est question de : à combien peut-on considérer un calcul comme exact en virgule flottante ?
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          7 avril 2010 à 10:39:58

                                          Je ne pense pas que Pi soit un nombre indispensable en géométrie. Il n'est pas constructible à la règle et au compas, donc si on utilise seulement ce genre d'opérations de base il n'y a pas de raison qu'il apparaisse comme distance entre deux points du plan.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                          Anonyme
                                            7 avril 2010 à 10:42:48

                                            Citation : bluestorm

                                            Je ne pense pas que Pi soit un nombre indispensable en géométrie. Il n'est pas constructible à la règle et au compas, donc si on utilise seulement ce genre d'opérations de base il n'y a pas de raison qu'il apparaisse comme distance entre deux points du plan.


                                            Pi est une valeur fondamentale : http://fr.wikipedia.org/wiki/Pi
                                            Oui elle se trouve dans les cercles mais aussi dans beaucoup de fractales naturelles comme les coquilles d'escargot ou autres éléments naturels.
                                            Donc pourquoi retrouver constamment un nombre si il n'est pas indispensable ?

                                            Après je veux pas digresser plus sur pi.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              7 avril 2010 à 10:55:39

                                              Non mais Pi a beau être une valeur fondamentale, ça ne veut pas dire qu'on doive le manipuler dans un logiciel de géométrie. L'utilisateur du logiciel ne va pas dessiner des fractales d'escargot infinies avant de demander la distance entre deux points de la fractale.

                                              La seule façon que je vois de faire apparaître Pi, c'est de permettre à l'utilisateur de calculer la longueur de courbes quelconques (et pas seulement la distance entre deux points de la figure). Dans ce cas, peut avoir Pi, mais on peut peut-être aussi se contenter de comparaison approchées : autant pour déterminer si deux points sont confondus ou non, il faut un calcul exact (donc symbolique), autant si l'utilisateur demande "est-ce que telle courbe est plus courte ou plus longue que telle autre", on peut peut-être se permettre une approximation.

                                              Encore une fois, tout dépend des fonctionnalités exacte qu'il veut mettre en place pour son logiciel, mais s'il s'agit de tracer des courbes usuelles (droites, cercles, parabole..) déterminées par des polynomes, et de calculer des intersections, je ne pense pas que Pi apparaisse parmi les coordonnées des points à manipuler.
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                9 avril 2010 à 16:01:25

                                                Est-ce que le pattern Interpreter serait adaptée pour une implémentation OO du calcul symbolique ?
                                                Et la performance est-elle vraiment au rendez-vous ? Par exemple si on utilise les fonctions de géométrie dans l'espace pour faire du raytracing en temps réel, ce sera bien trop lent non (par rapport aux flottants classiques) ?

                                                Merci.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                Administrateur du forum Paul Diel
                                                  9 avril 2010 à 19:41:32

                                                  Il me semble que quand tu fais du raytracing, tu fais des calculs approchés de toute façon et pas exacts, donc l'idée d'utiliser des représentation symbolique pour cela me semble un peu farfelue.

                                                  Ceci dit, tu peux toujours maintenir tes expressions symboliques pour avoir les valeurs exactes, mais passer aux valeurs flottantes avant chaque phase de dessin.
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    9 avril 2010 à 22:09:22

                                                    J'avais tourné le problème comme ça :
                                                    Il me faudrait utiliser une classe Rayon définie par un vecteur et un point. Mais pour déterminer si deux rayons sont parallèles, il faut comparer les coordonnées exactes des deux vecteurs directeurs.
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                    Administrateur du forum Paul Diel
                                                      9 avril 2010 à 22:19:06

                                                      Je ne connais essentiellement rien en raytracing, mais je ne vois pas où tu pourrais avoir besoin d'un test exact pour savoir si deux rayons sont parallèles.
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        10 avril 2010 à 12:07:00

                                                        Au temps pour moi, j'aurais dû réfléchir avant de poster.
                                                        En fait une bibliothèque de géométrie n'est pas du tout adaptée au raytracing.

                                                        EDIT : Toutefois, pour savoir si deux primitives se coupent, il me faut faire des tests d'égalité sur des flottants, donc introduire des marges d'erreur du genre epsilon (pardonnez ma méconnaissance)…
                                                        Mais comment savoir quelle marge d'erreur on peut utiliser, puisque la précision ne sera pas la même selon l'utilisateur ? Je m'explique : il y aura des gens qui feront des scènes au millimètre tandis que d'autres travailleront en mètres. et dans le premier cas, la marge d'erreur devra être moindre.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                        Administrateur du forum Paul Diel

                                                        Opérations sur les nombres flottants

                                                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                        × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                        • Editeur
                                                        • Markdown