Comment est implémentée Math.Pow() dans le .NET Framework?

Question

J'étais à la recherche d'une approche efficace pour calculer ab (disons a = 2 et b = 50). Pour commencer, j'ai décidé de jeter un coup d'œil à l'implémentation de la fonction Math.Pow(). Mais dans .NET Reflector, tout ce que j'ai trouvé était ceci :

[MethodImpl(MethodImplOptions.InternalCall), SecuritySafeCritical]
public static extern double Pow(double x, double y);

Quels sont les ressources où je peux voir ce qui se passe lorsque j'appelle la fonction Math.Pow() ?

Answer 1

MethodImplOptions.InternalCall

Cela signifie que la méthode est réellement implémentée dans le CLR, écrite en C++. Le compilateur juste-à-temps consulte une table avec des méthodes implémentées en interne et compile l'appel à la fonction C++ directement.

Jeter un œil au code nécessite le code source du CLR. Vous pouvez l'obtenir à partir de la distribution SSCLI20. Il a été écrit autour de la période de temps de .NET 2.0, j'ai trouvé que les implémentations de bas niveau, comme Math.Pow(), sont encore largement précises pour les versions ultérieures du CLR.

La table de recherche se trouve dans clr/src/vm/ecall.cpp. La section qui concerne Math.Pow() ressemble à cela :

FCFuncStart(gMathFuncs)
    FCIntrinsic("Sin", COMDouble::Sin, CORINFO_INTRINSIC_Sin)
    FCIntrinsic("Cos", COMDouble::Cos, CORINFO_INTRINSIC_Cos)
    FCIntrinsic("Sqrt", COMDouble::Sqrt, CORINFO_INTRINSIC_Sqrt)
    FCIntrinsic("Round", COMDouble::Round, CORINFO_INTRINSIC_Round)
    FCIntrinsicSig("Abs", &gsig_SM_Flt_RetFlt, COMDouble::AbsFlt, CORINFO_INTRINSIC_Abs)
    FCIntrinsicSig("Abs", &gsig_SM_Dbl_RetDbl, COMDouble::AbsDbl, CORINFO_INTRINSIC_Abs)
    FCFuncElement("Exp", COMDouble::Exp)
    FCFuncElement("Pow", COMDouble::Pow)
    // etc..
FCFuncEnd()

Rechercher "COMDouble" vous emmène à clr/src/classlibnative/float/comfloat.cpp. Je vous épargne le code, jetez-y un coup d'œil par vous-même. Fondamentalement, il vérifie les cas particuliers, puis appelle la version CRT de pow().

Le seul autre détail d'implémentation intéressant est le macro FCIntrinsic dans la table. C'est un indice que le jitter peut implémenter la fonction comme un intrinsèque. En d'autres termes, substituer l'appel de fonction par une instruction de code machine en virgule flottante. Ce n'est pas le cas pour Pow(), il n'y a pas d'instruction FPU pour cela. Mais certainement pour les autres opérations simples. À noter que cela peut rendre les mathématiques en virgule flottante en C# sensiblement plus rapides que le même code en C++, consultez cette réponse pour connaître la raison.

En passant, le code source pour le CRT est également disponible si vous avez la version complète du répertoire vc/crt/src de Visual Studio. Vous atteindrez cependant une impasse sur pow(), Microsoft a acheté ce code à Intel. Faire un meilleur travail que les ingénieurs d'Intel est peu probable. Bien que l'identité de mon livre de lycée était deux fois plus rapide lorsque j'ai essayé :

public static double FasterPow(double x, double y) {
    return Math.Exp(y * Math.Log(x));
}

Mais ce n'est pas un véritable substitut car cela accumule des erreurs à partir de 3 opérations en virgule flottante et ne traite pas les problèmes de domaine bizarres que Pow() a. Comme 0^0 et -Infinity élevé à n'importe quelle puissance.

Answer 2

La réponse de Hans Passant est excellente, mais je voudrais ajouter que si b est un entier, alors a^b peut être calculé de manière très efficace avec une décomposition binaire. Voici une version modifiée tirée de Hacker's Delight de Henry Warren :

public static int iexp(int a, uint b) {
    int y = 1;

    while(true) {
        if ((b & 1) != 0) y = a*y;
        b = b >> 1;
        if (b == 0) return y;
        a *= a;
    }    
}

Il note que cette opération est optimale (effectue le nombre minimum d'opérations arithmétiques ou logiques) pour tous les b < 15. De plus, il n'existe aucune solution connue au problème général de trouver une séquence optimale de facteurs pour calculer a^b pour tout b autre qu'une recherche exhaustive. C'est un problème NP-Difficile. Donc en gros, cela signifie que la décomposition binaire est aussi bien que possible.

Answer 3

Si la version C librement disponible de pow constitue un indicatif, cela ne ressemble en rien à ce à quoi vous vous attendez. Il ne vous sera pas d'une grande aide de trouver la version .NET, car le problème que vous résolvez (c'est-à-dire celui avec des entiers) est de loin plus simple, et peut être résolu en quelques lignes de code C# avec l'algorithme d'exponentiation par carrés.

Answer 4

En parcourant les réponses, j'ai beaucoup appris sur les calculs en arrière-plan : J'ai essayé quelques solutions sur une plateforme de codage qui a une couverture de tests extensive, et j'ai trouvé un moyen très efficace de le faire (Solution 3) :

public double MyPow(double x, int n) {
    double res = 1;
    /* Solution 1 : itératif : TLE (Dépassement de la limite de temps)
    double res = 1;
    var len = n > 0 ? n : -n;
    for(var i = 0; i < len; ++i)
        res *= x;   

    return n > 0 ? res : 1 / res; 
    */

    /* Solution 2 : récursif => dépassement de pile
    if(x == 0) return n > 0 ? 0 : 1 / x;
    if(n == 1) return x;

    return n > 0 ? x * MyPow(x, n - 1) : (1/x) * MyPow(1/x, -n); 
    */

    //Solution 3 :
    if (n == 0) return 1;

    var half = MyPow(x, n / 2);
    if (n % 2 == 0) 
        return half * half;
    else if (n > 0) 
        return half * half * x;
    else 
        return half * half / x;

    /* Solution 4 : à l'aide des bits => TLE (Dépassement de la limite de temps)
    var b = n > 0 ? n : -n;        
    while(true) {
        if ((b & 1) != 0) 
            res *= x;

        b = b >> 1;

        if (b == 0) break;

        x *= x;
    }   
    return n > 0 ? res : 1 / res; 
    */
}

Answer 5

Réponse acceptée sur Leetcode:

public class Solution {
    public double MyPow(double x, int n) {
        if(n==0) return 1;

        long abs = Math.Abs((long)n);

        var result = pow(x, abs);

        return n > 0 ? result : 1/result;
    }

    double pow(double x, long n){
        if(n == 1) return x;

        var result = pow(x, n/2);
        result = result * result * (n%2 == 1? x : 1);
        return result;
    }
}