实现基于整数的幂函数pow(int,int)的最有效方法

Question

将整数提升到C中另一个整数的幂的最有效方法是什么？

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

Answer 1

通过平方来表示.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

这是在非对称加密中对大量数进行模幂运算的标准方法.

Answer 2

请注意,通过平方取幂不是最佳方法.作为适用于所有指数值的通用方法,它可能是最好的,但对于特定的指数值,可能有更好的序列需要更少的乘法.

例如,如果你想计算x ^ 15,通过平方取幂的方法将给你:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

这是总共6次乘法.

事实证明,这可以通过加法链取幂使用"仅"5次乘法来完成.

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

没有有效的算法来找到这种最佳乘法序列.来自维基百科:

寻找最短加法链的问题不能通过动态规划来解决,因为它不满足最优子结构的假设.也就是说,将功率分解成较小的功率是不够的,每个功率都是最小的,因为较小功率的加法链可能是相关的(共享计算).例如,在上面a¹的最短加法链中,a⁶的子问题必须计算为(a³)²,因为a³被重新使用(相反,例如a⁶=a²(a²)²,这也需要三次乘法).

Answer 3

如果你需要提高2到一个功率.这样做的最快方法是按功率移位.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

Answer 4

这是Java中的方法

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

Answer 5

power()仅适用于整数的函数

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

复杂度 = O(log(exp))

power()用于负 exp 和 float base 的函数。

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

复杂度 = O(log(exp))

Answer 6

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

Answer 7

一个非常专业的情况是,当你需要说2 ^( - x到y)时,其中x当然是负的,y太大而不能在int上进行移位.你仍然可以通过拧一个浮子来在恒定时间内做2 ^ x.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

通过使用double作为基本类型,您可以获得更多2的幂.(非常感谢评论者帮助解决这个问题).

还有可能更多地了解IEEE浮点数,其他特殊的取幂情况可能会出现.

Answer 8

如果你想得到一个2的整数值,那么使用shift选项总是更好:

pow(2,5) 可以替换为 1<<5

这样效率更高.