c++ - 为什么 c 中的幂函数对于大数花费的时间比预期的要长

Question

我哪里弄错了？c/c++ 中的 pow(double,double) 函数在 O(log n) 时间内运行，这意味着计算长数的幂不会花费明显的时间。我写了一个函数来计算对数时间的 a^b mod m，这又比预期的要长。函数定义为:

float pow(float a,float n,float m){
  float temp,temp2;
  if(n==0)
    return 1;
  temp=pow(a,n/2,m);
  if(fmod(n,2)==0){
    if(temp>m){
      temp=fmod(temp,m);
    }
    temp2=temp*temp;
    if(temp2>m)
      temp2=fmod(temp2,m);
    return temp2;
  }
  else{
    if(temp>m){
      temp=fmod(temp,m);
    }
    temp2=temp*temp*a;
    if(temp2>m)
      temp2=fmod(temp2,m);
    return temp2;
  }
}

如果我调用 pow(10^9,10^9,123)，我希望它以 ~ O(log(10^9)) 的复杂度运行，因此在我的计算机上在 1 秒内完成(O(10^8)在 1 秒内运行)。但它需要永远。 std::pow(double,double) 也是如此。

Answer 1

因此，重复将 float 除以 2 只会在指数用完时完成。 (为了好玩，尝试传入 1.0f/0.0f。)

int func(float n) {
    if (n == 0)
        return 1;
    return 1 + func(n / 2);
}

在我的系统上，func(1.0f) 给出 151。这可能不是您想要的!

你想要这个:

float pow(float a, int n, float m) {
    if (n == 0)
        return 1.0f;
    float t = pow(a, n / 2, m);
    return fmodf((n & 1) ? t*t*a : t*t, m);
}

注意 pow() 是完全不同的。 pow() 的定义更接近于此:

float powf(float x, float y) {
    if (...) {
        // faster, special case versions
    }
    return expf(logf(x) * y);
}