IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Racine inverse - existe en C++ ?


Sujet :

C++

  1. #1
    Membre régulier

    Inscrit en
    juin 2008
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : juin 2008
    Messages : 49
    Points : 114
    Points
    114
    Par défaut Racine inverse - existe en C++ ?
    Bonsoir,

    J'ai un programme qui doit calculer entre autre la racine carrée inverse d'un nombre en simple ou double précision. Soit:

    et ceci des millions de fois. Des mesures avec callgrind montrent que le programme passe en effet près de 25% de son temps dans cette opération.

    La question que je me pose est de savoir si il existe une fonction permettant d'obtenir directement 1/sqrt(x) sans passer par sqrt(x) et une division ?
    Ou alors est-ce que le compilateur est capable d'optimiser cela en utilisant des instructions processeurs ?

    Auriez-vous des informations à ce sujet ?

    Merci d'avance !

    P.S.: Je ne cherche PAS des trucs approchés comme on trouve dans les jeux vidéo. J'ai besoin d'une solution aussi exacte que 1./sqrt(x).

  2. #2
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : juin 2006
    Messages : 2 307
    Points : 4 731
    Points
    4 731
    Par défaut
    Ce PDF devrait de brancher. Attention, ce ne sont pas des maths de bas niveau.

    P.S.: Je ne cherche PAS des trucs approchés comme on trouve dans les jeux vidéo. J'ai besoin d'une solution aussi exacte que 1./sqrt(x).
    Va faire des maths alors . En informatique, tu auras forcément une valeur approchée. Peut être à 10^(-10), 10^(-100) mais elle reste approchée.
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  3. #3
    Membre émérite
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    1 537
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : juillet 2006
    Messages : 1 537
    Points : 2 521
    Points
    2 521
    Par défaut
    La solution n'est précise qu'a 10^-3 près environs. Ce n'est donc pas ce que cherche notre homme.

    A priori, il est existe des instructions processeur pour faire cela. Pourquoi ne regardes-tu pas le code généré par le compilo afin de savoir si tu ne peux pas résoudre ton problème par des réglages compilo ? (pour g++ -O3 et -ffast-math)

  4. #4
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : juin 2006
    Messages : 2 307
    Points : 4 731
    Points
    4 731
    Par défaut
    Citation Envoyé par deadalnix Voir le message
    La solution n'est précise qu'a 10^-3 près environs. Ce n'est donc pas ce que cherche notre homme.

    A priori, il est existe des instructions processeur pour faire cela. Pourquoi ne regardes-tu pas le code généré par le compilo afin de savoir si tu ne peux pas résoudre ton problème par des réglages compilo ? (pour g++ -O3 et -ffast-math)
    La méthode proposée se base sur l'extraction de racines par la méthode de Newton, qui est un algorithme à convergence quadratique, donc si la précision n'est pas suffisante, il suffit de recommencer
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  5. #5
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 48
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Question bête : sachant que 1/sqrt(x) est égal à (x^(-1/2)), as-tu essayé un appel à pow avec -0.5 en guise d'exposant, pour voir ce que ça donne en terme de performances ?

    Sinon, faudrait peut-être regarder du côté des instructions SSE. Mais de mémoire, il n'y a pas d'opération native du FPU qui effectue directement 1/sqrt(x).
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  6. #6
    screetch
    Invité(e)
    Par défaut
    _mm_rsqrt_ps en SSE
    http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx
    sous GCC tu pourrais peut etre augmenter les perfs avec les options
    '-mfpmath=sse', '-msse2'

  7. #7
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    sous GCC tu pourrais peut etre augmenter les perfs avec les options
    '-mfpmath=sse', '-msse2'
    Il faut mieux donner le bon -march et laisser le compilo choisir le mieux
    Boost ftw

  8. #8
    Nouveau membre du Club
    Profil pro
    Inscrit en
    décembre 2007
    Messages
    33
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2007
    Messages : 33
    Points : 29
    Points
    29
    Par défaut
    Bonjour,
    Vous pourriez peut-être essayer de programmer ceci pour un calcul de 1/sqrt(x): si on considère que y est une valeur approchée,on pose (y+a)^2=1./x et on approxime par y^2+2*a*y=1./x d'où a = (1./(x*y)-y)/2.,on fait y=y+a,et on itère avec un test de convergence.
    A la question de l'initialisation de y,je pense que,si on sait identifier l'exposant et la mantisse de x,on pourrait prendre la même mantisse pour y(initial) et pour exposant l'exposant de x divisé par -2.

  9. #9
    Membre émérite
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    1 537
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : juillet 2006
    Messages : 1 537
    Points : 2 521
    Points
    2 521
    Par défaut
    Citation Envoyé par Davidbrcz Voir le message
    La méthode proposée se base sur l'extraction de racines par la méthode de Newton, qui est un algorithme à convergence quadratique, donc si la précision n'est pas suffisante, il suffit de recommencer
    Ça sera de toute façon moins rapide et moins précis que l'instruction cablée.

  10. #10
    Nouveau membre du Club
    Profil pro
    Inscrit en
    décembre 2007
    Messages
    33
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2007
    Messages : 33
    Points : 29
    Points
    29
    Par défaut
    Il est certain que,si l'instruction est câblée,la discussion sur une méthode logicielle n'a plus lieu.Bien sûr,quand je pensais à une méthode logicielle,c'est parce que je pensais qu'on supposait a priori que ce n'était pas le cas.C'était l'intérêt de la question initiale.Si la fonction sqrt() est câblée,la discussion est close d'elle-même.

  11. #11
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2009
    Messages : 560
    Points : 632
    Points
    632
    Par défaut
    La question serait plutôt amha pourquoi tu passe 25% de ton temps dans 4 lignes d'assembleur ?
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  12. #12
    Futur Membre du Club
    Inscrit en
    janvier 2010
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 8
    Points : 9
    Points
    9
    Par défaut
    Citation Envoyé par screetch Voir le message
    _mm_rsqrt_ps en SSE
    http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx
    sous GCC tu pourrais peut etre augmenter les perfs avec les options
    '-mfpmath=sse', '-msse2'
    Cette instruction fait en effet le travail, mais elle est relativement imprécise: environ 11 bits sur 24 sont significatifs.
    Il est donc nécessaire soit de refaire une itération de Newton-Raphson, soit de passer par la racine plus précise puis par la division (_mm_sqrt_ps puis _mm_div_ps) (ce qui est beaucoup plus long - cf. guide d'optimisation Intel: http://www.intel.com/products/proces...uals/index.htm).

  13. #13
    Membre régulier

    Inscrit en
    juin 2008
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : juin 2008
    Messages : 49
    Points : 114
    Points
    114
    Par défaut
    Merci pour vos réponses.

    pow(x,-0.5); est plus lent et de beaucoup.

    Pour les instructions SSE, je n'ai pas vu de différence notable. Je ne sais pas si le compilateur ne les activait pas par défaut.

  14. #14
    Membre émérite

    Inscrit en
    mai 2008
    Messages
    1 014
    Détails du profil
    Informations forums :
    Inscription : mai 2008
    Messages : 1 014
    Points : 2 252
    Points
    2 252
    Par défaut
    Citation Envoyé par Nanoc Voir le message
    Pour les instructions SSE, je n'ai pas vu de différence notable. Je ne sais pas si le compilateur ne les activait pas par défaut.
    C'est bizarre, non ?
    Je n'y connais pas grand chose en SSE, mais a priori ces instructions permettent de faire quatre racine inverse en une passe.

    Avec le test naïf ci-dessous, avec vs2010, j'obtiens bien un boost x4 :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
     
    #include <windows.h>
    #include <iostream>
     
    #include <cmath>
    #include "xmmintrin.h"
     
    #define LENGTH 100000000
     
    void TestInvSqrt()
    {
       double d = 0;
       for(int i = 1 ; i < LENGTH ; i++)
       {
          d += 1/sqrt((double)i);
       }
       printf("%f\n", d);
    }
     
     
    void TestInvSqrt2()
    {
       double d = 0;
       for(int i = 1 ; i < LENGTH ; i+=4)
       {
          __declspec(align(16)) float tab[4] = {i, i +1, i+2, i+3};
          __m128* m128 = (__m128*)tab;
          *m128 = _mm_rsqrt_ps(*m128);
     
          d += tab[0] + tab[1] + tab[2] + tab[3];
       }
       printf("%f\n", d);
    }
     
     
    int main()
    {
       int time  = GetTickCount();
       TestInvSqrt();
       std::cout << GetTickCount() - time << std::endl; 
     
       time  = GetTickCount();
       TestInvSqrt2();
       std::cout << GetTickCount() - time << std::endl;
    }

  15. #15
    Futur Membre du Club
    Inscrit en
    janvier 2010
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 8
    Points : 9
    Points
    9
    Par défaut
    Citation Envoyé par Arzar Voir le message
    C'est bizarre, non ?
    Je n'y connais pas grand chose en SSE, mais a priori ces instructions permettent de faire quatre racine inverse en une passe.

    Avec le test naïf ci-dessous, avec vs2010, j'obtiens bien un boost x4 :
    Nanoc, comme vient de le montrer Arzar, c'est en utilisant explicitement les instructions SIMD (version packed, pas scalaire) que tu obtiendras vraiment des gains.

    Activer les intrinsèques dans les options permet au compilateur de les utiliser, mais il ne parallélisera pas pour toi - à moins d'utiliser ICC (un de leurs arguments de vente est la parallélisation automatique).

    edit: Note: comme je le précisais plus haut, utiliser seulement _mm_rsqrt_ps ne te permet d'obtenir que 12 bits de précision. Si ça te suffit, tant mieux. Sinon, un raffinage reste à faire.

    edit2: mais de toute façon, si tu passes en SIMD, tu peux probablement commencer avec les instructions câblées et précises. Si le reste de ton calcul est parallélisable aussi, tu as des gains bien plus grand à espérer.

  16. #16
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2009
    Messages : 560
    Points : 632
    Points
    632
    Par défaut
    Je vais finir par croire qu'ils ont raison, un peu de théorie ne fait pas de mal >< !

    SSE, historiquement, c'est pour de la 3D. Du coup, cela PERMET le parallélisme, ou pour être plus exact, de la vectorisation. A ma connaissance, GCC depuis GCC 4 introduit la vectorisation automatique pour SSE et SSE2 >< !

    Après, si c'est vectorisable, en fonction de comment, soit on fait les opérations sur GPU (OpenCL), soit on se contente des instructions SSE... Mais comme déjà dit, GCC le fait pour toi normalement. Visual, je sais pas.

    Reste la façon d'activer les instruction SSE. C'est un truc qui m'ennuie au plus au point personnellement.

    Si tu utilise un -march approprié, tu les actives (car elles sous-entendent -msse[x]).

    Tu peux aussi utilise -msse[x], histoire de sélectionné non pas une architecture, mais juste les truc requis.

    La doc dis qu'il faut mettre -mpfmath=sse pour les utiliser automatiquement, mais sans ça, il les utilise quand même >< ??? (c'est ça le truc ennuyant car pas clair du tout).

    Une chose dont je suis pas certain, c'est que la version "imprécise" nécessite -funsafe-math-optimizations. Je dirais que c'est ce qui me parait logique.

    Bon ça résout pas tout. L'important étant surtout de savoir si c'est normal que tu fasse autant de division.
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  17. #17
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 48
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par Lavock Voir le message
    Visual, je sais pas.
    Visual utilise surtout les SSE (de façon automatique) pour optimiser les calculs en flottant et/ou entiers, mais pas spécialement pour paralléliser à ta place : http://msdn.microsoft.com/fr-fr/library/7t5yh4fd.aspx

    Pour le reste, VS fournit les fonctions intrinsèques de commande directe des copros SSE, ce qui permet de construire directement des boucles parallèles utilisant ces registres.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

Discussions similaires

  1. Racine carrée inverse
    Par billoux70 dans le forum VB 6 et antérieur
    Réponses: 1
    Dernier message: 01/10/2009, 16h35
  2. ldap L'entrée racine n'existe pas
    Par inlee dans le forum Réseau
    Réponses: 0
    Dernier message: 24/04/2008, 13h04
  3. Existe t-il une balise qui fasse l'inverse de <noscript>
    Par vincent.b dans le forum Général JavaScript
    Réponses: 1
    Dernier message: 19/05/2007, 10h55
  4. Réponses: 2
    Dernier message: 17/02/2007, 05h43
  5. Existe-til une ou plusieures racines?
    Par frechy dans le forum XML/XSL et SOAP
    Réponses: 2
    Dernier message: 11/05/2005, 15h10

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo