How is Math.Pow() implemented in .NET Framework?

Question

I was looking for an efficient approach for calculating a^b (say a = 2 and b = 50). To start things up, I decided to take a look at the implementation of Math.Pow() function. But in .NET Reflector, all I found was this:

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

What are some of the resources wherein I can see as what's going on inside when I call Math.Pow() function?

Answer 1

MethodImplOptions.InternalCall

That means that the method is actually implemented in the CLR, written in C++. The just-in-time compiler consults a table with internally implemented methods and compiles the call to the C++ function directly.

Having a look at the code requires the source code for the CLR. You can get that from the SSCLI20 distribution. It was written around the .NET 2.0 time frame, I've found the low-level implementations, like Math.Pow() to be still largely accurate for later versions of the CLR.

The lookup table is located in clr/src/vm/ecall.cpp. The section that's relevant to Math.Pow() looks like this:

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

Searching for "COMDouble" takes you to clr/src/classlibnative/float/comfloat.cpp. I'll spare you the code, just have a look for yourself. It basically checks for corner cases, then calls the CRT's version of pow().

The only other implementation detail that's interesting is the FCIntrinsic macro in the table. That's a hint that the jitter may implement the function as an intrinsic. In other words, substitute the function call with a floating point machine code instruction. Which is not the case for Pow(), there is no FPU instruction for it. But certainly for the other simple operations. Notable is that this can make floating point math in C# substantially faster than the same code in C++, check this answer for the reason why.

By the way, the source code for the CRT is also available if you have the full version of Visual Studio vc/crt/src directory. You'll hit the wall on pow() though, Microsoft purchased that code from Intel. Doing a better job than the Intel engineers is unlikely. Although my high-school book's identity was twice as fast when I tried it:

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

But not a true substitute because it accumulates error from 3 floating point operations and doesn't deal with the weirdo domain problems that Pow() has. Like 0^0 and -Infinity raised to any power.

Answer 2

Hans Passant's answer is great, but I would like to add that if b is an integer, then a^b can be computed very efficiently with binary decomposition. Here's a modified version from Henry Warren's 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;
    }    
}

He notes that this operation is optimal (does the minimum number of arithmetic or logical operations) for all b < 15. Also there is no known solution to the general problem of finding an optimal sequence of factors to compute a^b for any b other than an extensive search. It's an NP-Hard problem. So basically that means that the binary decomposition is as good as it gets.

Answer 3

If freely available C version of pow is any indication, it does not look like anything you would expect. It would not be of much help to you to find the .NET version, because the problem that you are solving (i.e. the one with integers) is orders of magnitudes simpler, and can be solved in a few lines of C# code with the exponentiation by squaring algorithm.

Answer 4

Going through the answers, learned a lot about behind-the-scene calculations: I've tried some workarounds on a coding platform which has an extensive test coverage cases, and found a very effective way doing it(Solution 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

Answer that is accepted on 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;
    }
}