代码之家 › 专栏 › 技术社区 › Doug T.

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

exponentiation math algorithm c

220

Doug T. · 技术社区 · 16 年前

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

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

17 回复 | 直到 9 年前

421

John Zwinck 6 年前

平方求幂。

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

    return result;
}

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

ReinstateMonica3167040 OurangZeb Khan 7 年前

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

例如,如果要计算x^15,则通过平方求幂的方法将提供:

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

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²),也需要三倍)。

Jake 13 年前

如果你需要将2提升到一个幂。实现这一点的最快方法是通过电源进行位移位。

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

user1067920 12 年前

下面是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;
}

Chris Cudmore 10 年前

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

roottraveller 8 年前

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(对数(经验))

权力() 负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(对数(经验))

Doug T. 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);
}

使用双精度作为基本类型可以获得更多的2次幂。

IEEE floats ,则可能会出现其他特殊的求幂情况。

Kevin Bedell 12 年前

如果要将2的整数值提升为某事物的幂,最好使用shift选项:

pow(2,5) 可以用 1<<5

这是更有效的。

Jason Z 16 年前

作为对平方求幂效率评论的后续。

这种方法的优点是它以日志(n)时间运行。例如,如果你要计算一些巨大的东西,比如x^1048575(2^20-1),你只需要通过循环20次,而不是使用简单的方法计算100多万次。

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

编辑:

chux - Reinstate Monica 7 年前

迟到的人:

y < 0 尽可能的好。

它使用的结果是 intmax_t 用于最大范围。没有规定不适合的答案 intmax\U t .
powjii(0, 0) --> 1 哪一个是 common result

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。

Abhijit Gaikwad 10 年前

考虑负指数网的更一般解

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

ToxicAbe 3 年前

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

}

Vaibhav Fouzdar 10 年前

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

kyorilys 9 年前

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

alx - recommends codidact 5 年前

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

下面是一个经过修改的平方幂运算版本,它也适用于有符号整数类型,并且不会给出错误的值:

#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 sqrt() 到 int INT_MAX

rank1 5 年前

我已经实现了一个算法,它可以记住所有计算出的幂,然后在需要时使用它们。例如,x^13等于(x^2)^2^2*x^2^2*x,其中x^2^2是从表中提取的,而不是再次计算。这基本上是@Pramod answer的实现(但在C#中)。所需的乘法数为Ceil(对数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);
}

user1095108 3 年前

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

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

-1

MarcusJ 8 年前

我的情况有点不同,我试图用电源制作一个面具,但我想我还是会分享我找到的解决方案。

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

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

-1

Johannes Blaschke 6 年前

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

需要在运行时知道指数,

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}