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

Question

Ich war auf der Suche nach einem effizienten Ansatz zur Berechnung einer b (sagen a = 2 y b = 50 ). Um die Dinge in Gang zu bringen, habe ich beschlossen, einen Blick auf die Implementierung von Math.Pow() Funktion. Aber in .NET-Reflektor fand ich nur dies:

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

Was sind einige der Ressourcen, bei denen ich sehen kann, was im Inneren vor sich geht, wenn ich anrufe Math.Pow() Funktion?

Answer 1

MethodImplOptions.InternalCall

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

Um einen Blick auf den Code zu werfen, ist der Quellcode der CLR erforderlich. Diesen können Sie aus dem SSCLI20-Verteilung . NET 2.0 geschrieben wurde, habe ich die Low-Level-Implementierungen gefunden, wie Math.Pow() für spätere Versionen der CLR noch weitgehend zutreffend zu sein.

Die Nachschlagetabelle befindet sich in clr/src/vm/ecall.cpp. Der Abschnitt, der für Math.Pow() sieht so 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()

Die Suche nach "COMDouble" führt Sie zu clr/src/classlibnative/float/comfloat.cpp. Ich erspare Ihnen den Code, schauen Sie ihn sich einfach selbst an. Im Grunde prüft er auf Eckfälle und ruft dann die CRT-Version von pow() .

Das einzige andere interessante Detail der Implementierung ist das FCIntrinsic-Makro in der Tabelle. Das ist ein Hinweis darauf, dass der Jitter die Funktion als Intrinsic implementieren kann. Mit anderen Worten: Ersetzen Sie den Funktionsaufruf durch eine Gleitkomma-Maschinencode-Anweisung. Dies ist nicht der Fall bei Pow() gibt es keinen FPU-Befehl für sie. Aber für die anderen einfachen Operationen schon. Bemerkenswert ist, dass dies Fließkomma-Mathematik in C# wesentlich schneller machen kann als den gleichen Code in C++, siehe diese Antwort für den Grund dafür.

Übrigens ist der Quellcode für den CRT auch verfügbar, wenn Sie die Vollversion von Visual Studio im Verzeichnis vc/crt/src haben. Sie stoßen auf die Wand bei pow() Allerdings hat Microsoft diesen Code von Intel gekauft. Es ist unwahrscheinlich, dass sie es besser machen als die Intel-Ingenieure. Obwohl die Identität meines Highschool-Buches doppelt so schnell war, als ich es ausprobiert habe:

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

Aber es ist kein echter Ersatz, weil es Fehler aus 3 Fließkommaoperationen akkumuliert und nicht mit den seltsamen Domänenproblemen zu tun hat, die Pow() hat. Wie z.B. 0^0 und -Infinity erhöht auf eine beliebige Potenz.

Answer 2

Die Antwort von Hans Passant ist großartig, aber ich möchte hinzufügen, dass, wenn b eine ganze Zahl ist, dann a^b kann mit binärer Zerlegung sehr effizient berechnet werden. Hier ist eine modifizierte Version aus Henry Warrens Hackerfreuden :

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 geringste Anzahl von arithmetischen oder logischen Operationen). Es gibt auch keine bekannte Lösung für das allgemeine Problem, eine optimale Folge von Faktoren zu finden, um zu berechnen a^b für ein beliebiges b, außer einer umfangreichen Suche. Es ist ein NP-schweres Problem. Das bedeutet also, dass die binäre Zerlegung so gut ist, wie sie nur sein kann.

Answer 3

Si frei verfügbare C-Version von pow ist ein Hinweis darauf, dass es nicht so aussieht, wie man es erwarten würde. Es würde Ihnen nicht viel helfen, die .NET-Version zu finden, denn das Problem, das Sie lösen wollen (d. h. das mit den ganzen Zahlen), ist um Größenordnungen einfacher und kann mit ein paar Zeilen C#-Code gelöst werden mit dem Algorithmus Potenzieren durch Quadrieren .

Answer 4

Beim Durchgehen der Antworten habe ich viel über die Berechnungen hinter den Kulissen gelernt: Ich habe einige Workarounds auf einer Kodierungsplattform ausprobiert, die über eine umfangreiche Testabdeckung verfügt, und eine sehr effektive Methode gefunden (Lösung 3):

public double MyPow(double x, int n) {
    double res = 1;
    /* Solution 1: iterative : TLE(Time Limit Exceeded)
    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: recursive => stackoverflow exception
    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: bitwise=> TLE(Time Limit Exceeded)
    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

Antwort, die auf Leetcode akzeptiert wird:

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