444

我一直在寻找一种有效的方法来计算 a b（比如a = 2and b = 50）。首先，我决定看一下Math.Pow()函数的实现。但是在.NET Reflector中，我发现的只是：

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

Math.Pow()当我调用函数时，我可以看到哪些资源在里面发生了什么？

4

4 回答 4

872

MethodImplOptions.InternalCall

这意味着该方法实际上是在 CLR 中实现的，用 C++ 编写。即时编译器使用内部实现的方法查询表，并直接编译对 C++ 函数的调用。

查看代码需要 CLR 的源代码。您可以从SSCLI20 发行版中获得它。它是围绕 .NET 2.0 时间框架编写的，我发现低级实现Math.Pow()对于 CLR 的更高版本仍然基本准确。

查找表位于 clr/src/vm/ecall.cpp 中。相关的部分Math.Pow()如下所示：

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

搜索“COMDouble”会将您带到 clr/src/classlibnative/float/comfloat.cpp。我把代码留给你，你自己看看。它基本上检查极端情况，然后调用 CRT 的pow().

唯一有趣的其他实现细节是表中的 FCIntrinsic 宏。这暗示抖动可能将该功能实现为内在函数。换句话说，用浮点机器代码指令替换函数调用。情况并非如此Pow()，它没有 FPU 指令。但肯定适用于其他简单的操作。值得注意的是，这可以使 C# 中的浮点数学比 C++ 中的相同代码快得多，请检查此答案以了解原因。

顺便说一句，如果您有完整版的 Visual Studio vc/crt/src 目录，也可以获得 CRT 的源代码。不过，您会碰壁pow()，微软从英特尔购买了该代码。比英特尔工程师做得更好是不可能的。虽然我的高中书的身份在我尝试的时候快了一倍：

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

但不是真正的替代品，因为它会累积来自 3 个浮点运算的错误，并且不处理 Pow() 所具有的怪异域问题。就像 0^0 和 -Infinity 提升到任何幂一样。

于 2012-01-15T14:52:59.350 回答
115

Hans Passant 的回答很好，但我想补充一点，如果b是一个整数，那么a^b可以通过二进制分解非常有效地计算。这是 Henry Warren 的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;
    }    
}

他指出，对于所有 b < 15，此操作是最优的（进行最少数量的算术或逻辑运算）。此外，a^b对于为任何 b 找到最佳因子序列来计算的一般问题，除了广泛的外，没有已知的解决方案。搜索。这是一个 NP-Hard 问题。所以基本上这意味着二进制分解是最好的。

于 2012-07-10T18:15:34.000 回答
71

如果免费提供的 C 版本pow有任何迹象，那么它看起来不像您所期望的那样。找到 .NET 版本对您没有多大帮助，因为您正在解决的问题（即整数问题）要简单几个数量级，并且可以用几行 C# 代码和求幂来解决通过平方算法。

于 2012-01-15T14:43:49.050 回答
0

通过答案，了解了很多关于幕后计算的知识：我在一个具有广泛测试覆盖案例的编码平台上尝试了一些解决方法，并找到了一种非常有效的方法（解决方案 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; 
    */
}
于 2020-07-16T14:49:54.317 回答