W jaki sposób Math.Pow () jest implementowany w .NET Framework?

432

Szukałem wydajnego podejścia do obliczania b (powiedz a = 2i b = 50). Na początek postanowiłem rzucić okiem na implementację Math.Pow()funkcji. Ale w .NET Reflector znalazłem tylko:

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

Jakie są zasoby, w których mogę zobaczyć, co się dzieje w środku, gdy wywołuję Math.Pow()funkcję?

Pawan Mishra
źródło
15
Podobnie jak w przypadku FYI, jeśli nie masz pewności co do całości InternalCallz externmodyfikatorem (ponieważ wydają się one być w konflikcie), zapoznaj się z pytaniem (i uzyskanymi odpowiedziami), które zamieściłem na ten temat.
CraigTP
6
W przypadku 2^xoperacji, która xjest liczbą całkowitą, wynikiem jest operacja przesunięcia. Więc może mógłbyś skonstruować wynik za pomocą mantysy 2i wykładnika x.
ja72
@SurajJain twój komentarz jest tak naprawdę pytaniem, które musisz wysłać osobno.
ja72
@SurajJain Zgadzam się z tobą. Nie jestem moderatorem, więc nie mogę tutaj wiele zrobić. Być może pytanie negatywne można zadać na stronie meta.stackoverflow.com
ja72

Odpowiedzi:

854

MethodImplOptions.InternalCall

Oznacza to, że metoda jest faktycznie zaimplementowana w CLR, napisanym w C ++. Kompilator just-in-time konsultuje tabelę z wewnętrznie zaimplementowanymi metodami i bezpośrednio kompiluje wywołanie funkcji C ++.

Spojrzenie na kod wymaga kodu źródłowego dla CLR. Możesz to uzyskać z dystrybucji SSCLI20 . Został napisany wokół ramy czasowej .NET 2.0. Znalazłem implementacje niskiego poziomu, które lubią Math.Pow()być w dużej mierze dokładne w późniejszych wersjach CLR.

Tabela odnośników znajduje się w clr / src / vm / ecall.cpp. Sekcja istotna dla Math.Pow()wygląda następująco:

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

Wyszukiwanie „COMDouble” prowadzi do clr / src / classlibnative / float / comfloat.cpp. Oszczędzę ci kodu, po prostu sprawdź. Zasadniczo sprawdza przypadki narożne, a następnie wywołuje wersję CRT pow().

Jedynym interesującym szczegółem implementacji jest makro FCIntrinsic w tabeli. To wskazówka, że ​​fluktuacja może implementować tę funkcję jako wewnętrzną. Innymi słowy, zastąp funkcję wywołania zmiennoprzecinkową instrukcją kodu maszynowego. To nie jest przypadek Pow(), nie ma instrukcji FPU. Ale z pewnością w przypadku innych prostych operacji. Warto zauważyć, że dzięki temu matematyka zmiennoprzecinkowa w języku C # jest znacznie szybsza niż ten sam kod w języku C ++, sprawdź tę odpowiedź z tego powodu.

Nawiasem mówiąc, kod źródłowy dla CRT jest również dostępny, jeśli masz pełną wersję katalogu Visual Studio vc / crt / src. Trafisz jednak na mur pow(), Microsoft kupił ten kod od Intela. Wykonywanie lepszej pracy niż inżynierowie Intela jest mało prawdopodobne. Chociaż tożsamość mojej licealnej książki była dwukrotnie szybsza, gdy jej spróbowałem:

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

Ale nie jest to prawdziwy substytut, ponieważ kumuluje błąd z 3 operacji zmiennoprzecinkowych i nie radzi sobie z dziwnymi problemami domenowymi Pow (). Jak 0 ^ 0 i -Niekończoność podniesiona do dowolnej potęgi.

Hans Passant
źródło
437
Świetna odpowiedź, StackOverflow potrzebuje więcej tego rodzaju rzeczy, zamiast „Dlaczego chcesz to wiedzieć?” to zdarza się zbyt często.
Tom W
16
@Blue - Nie wiem, krótko od żartowania z inżynierów Intela. Mój liceum ma problem z podniesieniem czegoś do potęgi ujemnej. Pow (x, -2) jest doskonale obliczalny, Pow (x, -2.1) jest niezdefiniowany. Problemy z domeną to dziwka, z którą trzeba sobie poradzić.
Hans Passant
12
@ BlueRaja-DannyPflughoeft: Dużo wysiłku włożono w zapewnienie, aby operacje zmiennoprzecinkowe były jak najbardziej zbliżone do poprawnie zaokrąglonej wartości. powjest niezwykle trudne do dokładnego wdrożenia, będąc funkcją transcendentalną (patrz Dylemat Twórcy Stołu ). Jest to o wiele łatwiejsze dzięki zintegrowanej mocy.
werandy
9
@Hans Passant: Dlaczego Pow (x, -2.1) byłby niezdefiniowany? Matematycznie pow jest definiowane wszędzie dla wszystkich x i y. Często otrzymujesz liczby zespolone dla ujemnego x i niecałkowitego y.
Jules
8
@Jules pow (0, 0) nie jest zdefiniowany.
wytłoczono
110

Odpowiedź Hansa Passanta jest świetna, ale chciałbym dodać, że jeśli bjest liczbą całkowitą, to a^bmożna ją bardzo skutecznie obliczyć z rozkładem binarnym. Oto zmodyfikowana wersja z Hacker's Delight Henry'ego Warrena :

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

Zauważa, że ​​ta operacja jest optymalna (wykonuje minimalną liczbę operacji arytmetycznych lub logicznych) dla wszystkich b <15. Również nie jest znane rozwiązanie ogólnego problemu znalezienia optymalnej sekwencji czynników do obliczenia a^bdla dowolnego b innego niż ekstensywne Szukaj. To trudny NP. Zasadniczo oznacza to, że rozkład binarny jest tak dobry, jak to tylko możliwe.

Michał Graczyk
źródło
11
Ten algorytm ( kwadrat i mnożenie ) ma również zastosowanie, jeśli ajest liczbą zmiennoprzecinkową.
CodesInChaos
14
W praktyce można zrobić coś znacznie lepszego niż natywny kwadrat i mnożenie. Na przykład przygotowywanie tabel odnośników dla małych wykładników, aby można było kwadratować kilka razy, a dopiero potem pomnożyć, lub budować zoptymalizowane łańcuchy dodawania kwadratów dla stałych wykładników. Ten rodzaj problemu stanowi integralną część ważnych algorytmów kryptograficznych, dlatego sporo pracy poświęcono na jego optymalizację. Twardość NP dotyczy tylko najgorszych przypadków asymptotyków , często możemy stworzyć optymalne lub prawie optymalne rozwiązania dla przypadków pojawiających się w praktyce.
CodesInChaos
Tekst nie wspomina o abyciu liczbą całkowitą, ale kod tak. W związku z tym zastanawiam się nad dokładnością wyniku „bardzo wydajnego” obliczenia tekstu.
Andrew Morton
69

Jeśli dowolnie dostępna wersja Cpow jest jakąkolwiek wskazówką, nie wygląda na nic, czego można by oczekiwać. Znalezienie wersji .NET nie przydałoby się zbytnio, ponieważ problem, który rozwiązujesz (tj. Ten z liczbami całkowitymi), jest o kilka rzędów wielkości prostszy i można go rozwiązać za pomocą potęgowania w kilku wierszach kodu C # algorytm kwadratu .

dasblinkenlight
źródło
Dzięki za odpowiedź. Pierwszy link zaskoczył mnie, ponieważ nie spodziewałem się tak ogromnej technicznej implementacji funkcji Pow (). Chociaż odpowiedź Hansa Passanta potwierdza, że ​​jest tak samo w świecie .Net. Myślę, że mogę rozwiązać problem, korzystając z niektórych technik wymienionych w linku algorytmu kwadratu. Dzięki jeszcze raz.
Pawan Mishra
2
Nie wierzę, że ten kod jest wydajny. 30 zmiennych lokalnych powinno po prostu zniszczyć wszystkie rejestry. Przypuszczam tylko, że jest to wersja ARM, ale na x86 30 zmiennych lokalnych w metodzie jest niesamowita.
Alex Zhukovskiy,