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

通过平方进行指数运算。

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

    return result;
}

这是在非对称密码学中对巨大数字进行模幂运算的标准方法。

注意 exponentiation by squaring 不是最理想的方法。作为一种适用于所有指数值的通用方法,这可能是你能做的最好的事情,但对于特定的指数值,可能有一个需要更少乘法的更好的序列。

例如,如果你想计算x^15,平方求幂的方法会给你:

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

这总共是6次乘法。

事实证明,这可以通过“只”5次乘法来完成 addition-chain exponentiation .

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

没有有效的算法来找到这个最优的乘法序列。来自 Wikipedia :

动态规划无法解决寻找最短加法链的问题,因为它不满足最优子结构的假设。也就是说,将功率分解为较小的功率是不够的,每个功率都是最低限度地计算的,因为较小功率的加法链可能是相关的(以共享计算)。例如,在上述a的最短加法链中,a的子问题必须计算为(a),因为a被重复使用(与a=a(a)相反,a=a也需要三次乘法)。

如果你需要将2提升到幂。最快的方法是通过功率进行位偏移。

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

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

一个非常特殊的情况是,当你需要2^(-x到y)时,其中x当然是负数,y太大而无法在整数上进行移位。你仍然可以通过使用浮点数在恒定时间内进行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 floats ,其他求幂的特殊情况可能会出现。

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

功率() 工作职能 负exp和浮点数 .

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

如果你想得到一个2的整数的幂次方,最好使用shift选项:

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

这要高效得多。

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

正如对平方求幂效率的评论的后续。

这种方法的优点是它在log(n)时间内运行。例如,如果你要计算一些巨大的东西,比如x^1048575(2^20-1),你只需要遍历循环20次,而不是使用朴素的方法计算100多万次。

此外,就代码复杂度而言,这比试图找到最佳乘法序列更简单,这是la Pramod的建议。

编辑:

我想在有人给我贴上溢出的标签之前,我应该澄清一下。这种方法假设你有某种巨大的库。

迟到的聚会:

下面是一个解决方案,也涉及 y < 0 尽其所能。

1. 它使用以下结果 intmax_t 以获得最大范围。对于不适合的答案,没有规定 intmax_t .
2. powjii(0, 0) --> 1 这是一个 common result 对于这种情况。

3. pow(0,negative) ,另一个未定义的结果,返回 INTMAX_MAX

   intmax_t powjii(int x, int y) {
     if (y < 0) {
       switch (x) {
         case 0:
           return INTMAX_MAX;
         case 1:
           return 1;
         case -1:
           return y % 2 ? -1 : 1;
       }
       return 0;
     }
     intmax_t z = 1;
     intmax_t base = x;
     for (;;) {
       if (y % 2) {
         z *= base;
       }
       y /= 2;
       if (y == 0) {
         break; 
       }
       base *= base;
     }
     return z;
   }
   

这段代码使用了一个永久循环 for(;;) 为了避免决赛 base *= base 这在其他循环解决方案中很常见。乘法是1)不需要的,2)可以 int*int 溢出即UB。

考虑负exponeet的更通用解

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

除了Elias的回答,当用有符号整数实现时,会导致未定义行为,当用无符号整数实现时高输入值不正确,

这是Exponential by Squareing的一个修改版本,它也适用于有符号整数类型,并且不会给出不正确的值:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

此功能的注意事项:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

如果要发生任何溢出或包裹, return 0;

使用 int64_t ,但任何宽度(有符号或无符号)都可以使用,只需稍加修改。但是,如果需要使用非固定宽度整数类型,则需要更改 SQRT_INT64_MAX 靠近 (int)sqrt(INT_MAX) (如果使用 int )或者类似的东西,应该优化,但它更丑陋,不是C常量表达式。同时铸造的结果 sqrt() 到a 国际性组织 由于在完美正方形的情况下浮点精度不是很好,但据我所知,没有任何实现 INT_MAX -或者任何类型的最大值——是一个完美的正方形,你可以接受。

Swift中的O(log N)解。..

// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int { 

    // 1. If the exponent is 1 then return the number (e.g a^1 == a)
    //Time complexity O(1)
    if exp == 1 { 
        return base
    }

    // 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
    //Time complexity O(log N)
    let tempVal = power(base, exp/2) 

    // 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
    //Time complexity O(1)
    return (exp % 2 == 1 ? base : 1) * tempVal * tempVal 

}

int pow(int const x, unsigned const e) noexcept
{
  return !e ? 1 : 1 == e ? x : (e % 2 ? x : 1) * pow(x * x, e / 2);
  //return !e ? 1 : 1 == e ? x : (((x ^ 1) & -(e % 2)) ^ 1) * pow(x * x, e / 2);
}

是的,它是递归的,但一个好的优化编译器会优化递归。

还有一个实现(Java)。可能不是最有效的解决方案,但迭代次数与指数解决方案相同。

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}

我使用递归,如果exp是偶数,5^10=25^5。

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

我已经实现了一种算法,可以存储所有计算出的功率,然后在需要时使用它们。例如,x^13等于(x^2)^2^2*x^2^2*x,其中x^2^ 2取自表,而不是再次计算。这基本上是@Pramod答案的实现(但用C#)。 所需的乘法次数为Ceil(Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

这是一个O(1)算法,用于计算 x ** y ,灵感来自 this comment 。它适用于32位签名 int .

对于较小的值 y ,它使用平方求幂。对于较大的值 y ,只有少数值 x 结果不会溢出。此实现使用查找表来读取结果,而无需计算。

在溢出时,C标准允许任何行为,包括崩溃。然而,我决定对LUT索引进行绑定检查,以防止内存访问违规,这可能是令人惊讶和不受欢迎的。

伪代码:

If `x` is between -2 and 2, use special-case formulas.
Otherwise, if `y` is between 0 and 8, use special-case formulas.
Otherwise:
    Set x = abs(x); remember if x was negative
    If x <= 10 and y <= 19:
        Load precomputed result from a lookup table
    Otherwise:
        Set result to 0 (overflow)
    If x was negative and y is odd, negate the result

C代码:

#define POW9(x) x * x * x * x * x * x * x * x * x
#define POW10(x) POW9(x) * x
#define POW11(x) POW10(x) * x
#define POW12(x) POW11(x) * x
#define POW13(x) POW12(x) * x
#define POW14(x) POW13(x) * x
#define POW15(x) POW14(x) * x
#define POW16(x) POW15(x) * x
#define POW17(x) POW16(x) * x
#define POW18(x) POW17(x) * x
#define POW19(x) POW18(x) * x

int mypow(int x, unsigned y)
{
    static int table[8][11] = {
        {POW9(3), POW10(3), POW11(3), POW12(3), POW13(3), POW14(3), POW15(3), POW16(3), POW17(3), POW18(3), POW19(3)},
        {POW9(4), POW10(4), POW11(4), POW12(4), POW13(4), POW14(4), POW15(4), 0, 0, 0, 0},
        {POW9(5), POW10(5), POW11(5), POW12(5), POW13(5), 0, 0, 0, 0, 0, 0},
        {POW9(6), POW10(6), POW11(6), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(7), POW10(7), POW11(7), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(8), POW10(8), 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(9), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(10), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    int is_neg;
    int r;

    switch (x)
    {
    case 0:
        return y == 0 ? 1 : 0;
    case 1:
        return 1;
    case -1:
        return y % 2 == 0 ? 1 : -1;
    case 2:
        return 1 << y;
    case -2:
        return (y % 2 == 0 ? 1 : -1) << y;
    default:
        switch (y)
        {
        case 0:
            return 1;
        case 1:
            return x;
        case 2:
            return x * x;
        case 3:
            return x * x * x;
        case 4:
            r = x * x;
            return r * r;
        case 5:
            r = x * x;
            return r * r * x;
        case 6:
            r = x * x;
            return r * r * r;
        case 7:
            r = x * x;
            return r * r * r * x;
        case 8:
            r = x * x;
            r = r * r;
            return r * r;
        default:
            is_neg = x < 0;
            if (is_neg)
                x = -x;
            if (x <= 10 && y <= 19)
                r = table[x - 3][y - 9];
            else
                r = 0;
            if (is_neg && y % 2 == 1)
                r = -r;
            return r;
        }
    }
}

我的情况有点不同,我试图用一种力量创造一个面具,但我想无论如何我都会分享我找到的解决方案。

显然,它只适用于2的幂。

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;