Wie ist Math.Pow () in .NET Framework implementiert?

432

Ich suchte nach einem effizienten Ansatz zur Berechnung von a b (say a = 2and b = 50). Um die Dinge anzufangen, habe ich mich entschlossen, einen Blick auf die Implementierung der Math.Pow()Funktion zu werfen . In .NET Reflector fand ich jedoch nur Folgendes:

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

Was sind einige der Ressourcen, in denen ich sehen kann, was im Inneren vor sich geht, wenn ich Math.Pow()function aufrufe?

Pawan Mishra
quelle
15
Wenn Sie als FYI über das Ganze InternalCallmit einem externModifikator verwechselt sind (da diese widersprüchlich zu sein scheinen ), lesen Sie bitte die Frage (und die daraus resultierenden Antworten) , die ich zu genau dieser Sache gepostet habe.
CraigTP
6
Für ein , 2^xwenn der Betrieb xist das Ergebnis eine ganze Zahl Schaltvorgang. Vielleicht könnten Sie das Ergebnis mit einer Mantisse von 2und einem Exponenten von konstruieren x.
Ja72
@SurajJain Ihr Kommentar ist eigentlich eine Frage, die Sie separat posten müssen.
Ja72
@ SurajJain Ich stimme dir zu. Ich bin kein Moderator, daher kann ich hier nicht viel tun. Vielleicht kann die Frage zu Downvote gefragt werden meta.stackoverflow.com
ja72

Antworten:

854

MethodImplOptions.InternalCall

Das bedeutet, dass die Methode tatsächlich in der in C ++ geschriebenen CLR implementiert ist. Der Just-in-Time-Compiler konsultiert eine Tabelle mit intern implementierten Methoden und kompiliert den Aufruf der C ++ - Funktion direkt.

Für einen Blick auf den Code ist der Quellcode für die CLR erforderlich. Sie können dies von der SSCLI20-Distribution erhalten . Es wurde um den .NET 2.0-Zeitrahmen herum geschrieben. Ich habe festgestellt, dass die Implementierungen auf niedriger Ebene Math.Pow()für spätere Versionen der CLR immer noch weitgehend genau sind.

Die Nachschlagetabelle befindet sich in clr / src / vm / ecall.cpp. Der Abschnitt, der für relevant ist, Math.Pow()sieht folgendermaßen aus:

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

Wenn Sie nach "COMDouble" suchen, gelangen Sie zu clr / src / classlibnative / float / comfloat.cpp. Ich werde Ihnen den Code ersparen, sehen Sie selbst. Grundsätzlich wird nach Eckfällen gesucht und dann die CRT-Version von aufgerufen pow().

Das einzige andere interessante Implementierungsdetail ist das FCIntrinsic-Makro in der Tabelle. Dies ist ein Hinweis darauf, dass der Jitter die Funktion möglicherweise als intrinsisch implementiert. Mit anderen Worten, ersetzen Sie den Funktionsaufruf durch eine Gleitkomma-Maschinencode-Anweisung. Was nicht der Fall ist Pow(), gibt es keine FPU-Anweisung dafür. Aber sicherlich für die anderen einfachen Operationen. Bemerkenswert ist, dass dies die Gleitkomma-Mathematik in C # wesentlich schneller machen kann als der gleiche Code in C ++. Überprüfen Sie diese Antwort auf den Grund dafür.

Der Quellcode für die CRT ist übrigens auch verfügbar, wenn Sie über die Vollversion des Verzeichnisses Visual Studio vc / crt / src verfügen. Sie werden jedoch an die Wand gehen pow(), Microsoft hat diesen Code von Intel gekauft. Es ist unwahrscheinlich, einen besseren Job als die Intel-Ingenieure zu machen. Obwohl die Identität meines Highschool-Buches doppelt so schnell war, als ich es versuchte:

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

Aber kein echter Ersatz, da es Fehler aus 3 Gleitkommaoperationen akkumuliert und sich nicht mit den verrückten Domänenproblemen befasst, die Pow () hat. Wie 0 ^ 0 und -Infinity, die zu einer beliebigen Potenz erhoben werden.

Hans Passant
quelle
437
Gute Antwort, StackOverflow braucht mehr davon, anstatt "Warum sollten Sie das wissen wollen?" das passiert allzu oft.
Tom W
16
@Blue - Ich weiß nicht, kurz bevor ich mich über Intel-Ingenieure lustig gemacht habe. Mein Highschool-Buch hat ein Problem damit, etwas in die Macht eines negativen Integrals zu bringen. Pow (x, -2) ist perfekt berechenbar, Pow (x, -2.1) ist undefiniert. Domain-Probleme sind eine Hündin zu behandeln.
Hans Passant
12
@ BlueRaja-DannyPflughoeft: Es wird viel Mühe darauf verwendet, sicherzustellen, dass Gleitkommaoperationen so nahe wie möglich am korrekt gerundeten Wert liegen. powist bekanntermaßen schwer genau zu implementieren, da es sich um eine transzendentale Funktion handelt (siehe Dilemma des Tischmachers ). Mit einer integralen Kraft ist es viel einfacher.
porges
9
@ Hans Passant: Warum sollte Pow (x, -2.1) undefiniert sein? Mathematisch ist pow überall für alle x und y definiert. Sie neigen dazu, komplexe Zahlen für negatives x und nicht ganzzahliges y zu erhalten.
Jules
8
@Jules pow (0, 0) ist nicht definiert.
Prägung
110

Die Antwort von Hans Passant ist großartig, aber ich möchte hinzufügen, dass wenn bes sich um eine Ganzzahl handelt, a^bdiese mit binärer Zerlegung sehr effizient berechnet werden kann. Hier ist eine modifizierte Version von Henry Warrens Hacker's Delight :

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;
    }    
}

Er stellt fest, dass diese Operation für alle b <15 optimal ist (die minimale Anzahl von arithmetischen oder logischen Operationen ausführt). Es ist auch keine Lösung für das allgemeine Problem bekannt, eine optimale Folge von Faktoren zu finden, die a^bfür ein anderes b als ein umfangreiches berechnet werden können Suche. Es ist ein NP-hartes Problem. Das bedeutet also im Grunde, dass die binäre Zerlegung so gut ist, wie es nur geht.

Michael Graczyk
quelle
11
Dieser Algorithmus ( Quadrat und Multiplikation ) gilt auch, wenn aes sich um eine Gleitkommazahl handelt.
CodesInChaos
14
In der Praxis ist es möglich, einiges besser zu machen als das native Quadrat-und-Multiplizieren. Bereiten Sie beispielsweise Nachschlagetabellen für kleine Exponenten vor, damit Sie mehrmals quadrieren und erst dann multiplizieren können, oder erstellen Sie optimierte quadratische Additionsketten für feste Exponenten. Diese Art von Problem ist ein wesentlicher Bestandteil wichtiger kryptografischer Algorithmen, daher wurde viel an deren Optimierung gearbeitet. Bei der NP-Härte geht es nur um Asymptotika im schlimmsten Fall. Oft können wir optimale oder nahezu optimale Lösungen für Fälle des in der Praxis auftretenden Problems finden.
CodesInChaos
Der Text erwähnt nicht, adass es sich um eine Ganzzahl handelt, der Code jedoch. Infolgedessen wundere ich mich über die Genauigkeit des Ergebnisses der "sehr effizienten" Berechnung des Textes.
Andrew Morton
69

Wenn die frei verfügbare C-Version vonpow ein Hinweis ist, sieht sie nicht wie erwartet aus. Es wäre für Sie nicht sehr hilfreich, die .NET-Version zu finden, da das Problem, das Sie lösen (dh das mit ganzen Zahlen), um Größenordnungen einfacher ist und mit der Potenzierung in wenigen Zeilen C # -Code gelöst werden kann durch Quadrieren des Algorithmus .

dasblinkenlight
quelle
Danke für deine Antwort. Der erste Link überraschte mich, da ich nicht mit einer derart massiven technischen Implementierung der Pow () - Funktion gerechnet hatte. Obwohl die Antwort von Hans Passant bestätigt, dass dies auch in der .Net-Welt der Fall ist. Ich denke, ich kann das vorliegende Problem lösen, indem ich einige der im Link zum Quadrierungsalgorithmus aufgeführten Techniken verwende. Danke noch einmal.
Pawan Mishra
2
Ich glaube nicht, dass dieser Code effizient ist. 30 lokale Variablen sollten nur alle Register stoßen. Ich nehme nur an, dass es sich um eine ARM-Version handelt, aber auf x86 sind 30 lokale Variablen in der Methode fantastisch.
Alex Zhukovskiy