Comment Math.Pow () est-il implémenté dans .NET Framework?

433

Je cherchais une approche efficace pour calculer un b (disons a = 2et b = 50). Pour commencer, j'ai décidé de jeter un œil à l'implémentation de la Math.Pow()fonction. Mais dans .NET Reflector , je n'ai trouvé que ceci:

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

Quelles sont les ressources sur lesquelles je peux voir ce qui se passe à l'intérieur lorsque j'appelle Math.Pow()fonction?

Pawan Mishra
la source
15
Tout comme pour info, si vous êtes confus à propos de l'ensemble InternalCallavec un externmodificateur (car ils semblent être en conflit), veuillez voir la question (et les réponses qui en résultent) que j'ai postée à propos de cette même chose.
CraigTP
6
Pour une 2^xopération if xest entier, le résultat est une opération de décalage. Alors peut-être pourriez-vous construire le résultat en utilisant une mantisse de 2et un exposant de x.
ja72
@SurajJain votre commentaire est en fait une question que vous devez publier séparément.
ja72
@SurajJain, je suis d'accord avec vous. Je ne suis pas un modérateur donc je ne peux pas faire grand-chose ici. Peut-être que la question de downvote
ja72

Réponses:

855

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.

L'examen du code nécessite le code source du CLR. Vous pouvez l'obtenir auprès de la distribution SSCLI20 . Il a été écrit autour de la période de temps .NET 2.0, j'ai trouvé les implémentations de bas niveau, comme Math.Pow()étant 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 est pertinente Math.Pow()ressemble à ceci:

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

La recherche de "COMDouble" vous amène à clr / src / classlibnative / float / comfloat.cpp. Je vais vous épargner le code, jetez un œil par vous-même. Il vérifie essentiellement les cas d'angle, puis appelle la version du CRT de pow().

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

Par ailleurs, le code source du CRT est également disponible si vous disposez de la version complète du répertoire Visual Studio vc / crt / src. Vous allez heurter le mur pow(), Microsoft a acheté ce code auprès d'Intel. Faire un meilleur travail que les ingénieurs Intel est peu probable. Bien que l'identité de mon livre de lycée était deux fois plus rapide lorsque je l'ai essayé:

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

Mais ce n'est pas un vrai substitut car il accumule les erreurs de 3 opérations en virgule flottante et ne traite pas les problèmes de domaine bizarre de Pow (). Comme 0 ^ 0 et -Infinity élevé à n'importe quelle puissance.

Hans Passant
la source
437
Excellente réponse, StackOverflow a besoin de plus de ce genre de chose, au lieu de 'Pourquoi voudriez-vous le savoir?' cela arrive trop souvent.
Tom W
16
@Blue - Je ne sais pas, à moins de se moquer des ingénieurs Intel. Mon livre de lycée a un problème pour élever quelque chose au pouvoir d'une intégrale négative. Pow (x, -2) est parfaitement calculable, Pow (x, -2.1) n'est pas défini. Les problèmes de domaine sont une chienne à traiter.
Hans Passant
12
@ BlueRaja-DannyPflughoeft: Beaucoup d'efforts sont consacrés à s'assurer que les opérations en virgule flottante sont aussi proches que possible de la valeur correctement arrondie. powest notoirement difficile à mettre en œuvre avec précision, étant une fonction transcendantale (voir le dilemme de Table-Maker ). C'est beaucoup plus facile avec une puissance intégrale.
porges
9
@Hans Passant: Pourquoi Pow (x, -2.1) ne serait-il pas défini? La puissance mathématique est définie partout pour tous les x et y. Vous avez tendance à obtenir des nombres complexes pour x négatifs et y non entiers.
Jules
8
@Jules pow (0, 0) n'est pas défini.
graver le
110

La réponse de Hans Passant est excellente, mais je voudrais ajouter que si best un entier, alors il a^bpeut être calculé très efficacement avec une décomposition binaire. Voici une version modifié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 (fait le nombre minimum d'opérations arithmétiques ou logiques) pour tous les b <15. De plus, il n'y a pas de solution connue au problème général de trouver une séquence optimale de facteurs à calculer a^bpour tout b autre qu'un vaste chercher. C'est un problème NP-Hard. Donc, fondamentalement, cela signifie que la décomposition binaire est aussi bonne que possible.

Michael Graczyk
la source
11
Cet algorithme ( carré et multiplié ) s'applique également s'il as'agit d'un nombre à virgule flottante.
CodesInChaos
14
En pratique, il est possible de faire un peu mieux que le carré et la multiplication natifs. Par exemple, préparer des tables de recherche pour les petits exposants afin que vous puissiez quadriller plusieurs fois et ensuite seulement multiplier, ou créer des chaînes d'addition carrées optimisées pour les exposants fixes. Ce type de problème fait partie intégrante d'algorithmes cryptographiques importants, il y a donc eu pas mal de travail pour l'optimiser. La dureté NP ne concerne que les asymptotiques les plus défavorables , nous pouvons souvent produire des solutions optimales ou quasi optimales pour les cas de problème survenant dans la pratique.
CodesInChaos
Le texte ne mentionne pas aêtre un entier, mais le code le fait. En conséquence, je m'interroge sur la précision du résultat du calcul "très efficace" du texte.
Andrew Morton
69

Si la version C disponible gratuitementpow est une indication, elle ne ressemble à rien de ce que vous attendez. Il ne vous serait pas très utile de trouver la version .NET, car le problème que vous résolvez (c'est-à-dire celui avec des entiers) est de l'ordre de grandeur plus simple et peut être résolu en quelques lignes de code C # avec l'exponentiation par l'algorithme de quadrature .

dasblinkenlight
la source
Merci pour votre réponse. Le premier lien m'a surpris car je ne m'attendais pas à une implémentation technique aussi massive de la fonction Pow (). Bien que la réponse de Hans Passant confirme que c'est la même chose dans le monde .Net aussi. Je pense que je peux résoudre le problème actuel en utilisant certaines des techniques répertoriées dans le lien de l'algorithme de mise au carré. Merci encore.
Pawan Mishra du
2
Je ne pense pas que ce code soit efficace. 30 variables locales devraient juste bump tous les registres. Je suppose seulement que c'est la version ARM, mais sur x86, 30 variables locales dans la méthode sont impressionnantes.
Alex Zhukovskiy