浮点数指数幂运算无需使用幂函数

Question

目前我必须在一个存在 power-operator 缺陷的环境中工作。有没有人能想出一种临时性的方法来解决这个问题并计算 a^b（均为浮点数），而不使用 power 函数或运算符？

- ymihere

---

'b'会一直是整数吗？如果是，那么只需从1开始，将其乘以a，重复b次。 - Tom Sirgedas

a和b都是浮点数，不是自然数。 - ymihere

你有sqrt()可用吗？ - Tom Sirgedas

Answer 1

如果你可以使用sqrt()函数：

double sqr( double x ) { return x * x; }
// meaning of 'precision': the returned answer should be base^x, where
//                         x is in [power-precision/2,power+precision/2]
double mypow( double base, double power, double precision )
{   
   if ( power < 0 ) return 1 / mypow( base, -power, precision );
   if ( power >= 10 ) return sqr( mypow( base, power/2, precision/2 ) );
   if ( power >= 1 ) return base * mypow( base, power-1, precision );
   if ( precision >= 1 ) return sqrt( base );
   return sqrt( mypow( base, power*2, precision*2 ) );
}
double mypow( double base, double power ) { return mypow( base, power, .000001 ); }

测试代码：

void main()
{
   cout.precision( 12 );
   cout << mypow( 2.7, 1.23456 ) << endl;
   cout << pow  ( 2.7, 1.23456 ) << endl;
   cout << mypow( 1.001, 1000.7 ) << endl;
   cout << pow  ( 1.001, 1000.7 ) << endl;
   cout << mypow( .3, -10.7 ) << endl;
   cout << pow  ( .3, -10.7 ) << endl;
   cout << mypow( 100000, .00001 ) << endl;
   cout << pow  ( 100000, .00001 ) << endl;
   cout << mypow( 100000, .0000001 ) << endl;
   cout << pow  ( 100000, .0000001 ) << endl;
}

输出：

3.40835049344
3.40835206431
2.71882549461
2.71882549383
393371.348073
393371.212573
1.00011529225
1.00011513588
1.00000548981
1.00000115129

- Tom Sirgedas

---

非常感谢。这正是我正在寻找的。顺便问一下：您能给我介绍一下该算法的背景吗？ - ymihere

基本思想是 x^.5 = sqrt(x)，x^.25 = sqrt(sqrt(x))，x^.125 = sqrt(sqrt(sqrt(x))) 等等。利用这些构建块，我们可以说 x^.625 = (x^.5)*(x^.125)。我们无法精确表达 x^.3，但我们可以无限接近。我实现了略有不同，但使用了相同的概念。 - Tom Sirgedas

请注意，如果您的sqrt函数具有与std :: sqrt相同的限制，则对于负基数，此方法将无法使用。 - Drag-On

我喜欢你的想法，但我认为它可以在时间和空间复杂度上更好地完成。迭代版本可以将空间节省到O(1)，时间可以提高到O(log(n))。 - Sean Tashlik

顺便提一下，您可以按照 https://dev59.com/iXA75IYBdhLWcg3w49YR#3047531 中的方法实现sqrt。 - Eduard Grigoryev

Answer 2

您可以使用恒等式a^b = e^(bloga)，这样所有的计算都是相对于同一个底数e = 2.71828……

现在您需要实现f(x) = ln(x)，和g(x) = e^x。快速低精度的方法是使用f(x)和g(x)的查找表。也许那已经足够满足您的需求了。如果不行，您可以使用泰勒级数展开来用乘法和加法表示ln(x)和e^x。

- Jim Lewis

---

我有一个可用的ln函数。但是，为了使用泰勒级数，我需要再次使用幂函数。 - ymihere

@ymihere：泰勒级数展开只包含整数指数，可以简化为乘法。 - Jim Lewis

@ymihere：你有可用的exp()函数吗？如果有，这个解决方案是最好的！ - Tom Sirgedas

@tom：我没有经验。实际上，这就是我正在努力解决的问题。 - ymihere

Answer 3

假设您可以使用sqrt，这个简单的递归算法可以工作：

假设我们正在计算a的b次方。该算法的工作方式是对指数执行快速指数运算，直到达到小数部分，在小数部分中，执行修改后的二分搜索，直到接近小数部分。

double EPS = 0.0001;

double exponentiation(double base, double exp){
  if(exp >= 1){
    double temp = exponentiation(base, exp / 2);
    return temp * temp;
  } else{
    double low = 0;
    double high = 1.0;

    double sqr = sqrt(base);
    double acc = sqr;    
    double mid = high / 2;

    while(abs(mid - exp) > EPS){
      sqr = sqrt(sqr);

      if (mid <= exp) {
          low = mid;
          acc *= sqr;
      } else{
          high = mid;
          acc *= (1/sqr);
      }

      mid = (low + high) / 2;
    }

    return acc;
  }
}

- eapolinario