我正在尝试确定我的一种算法的渐进运行时间，该算法使用指数，但是我不确定如何以编程方式计算指数。

我专门在寻找用于双精度浮点数的pow()算法。

解决方案

通常的方法是将a提高到b，以获得整数指数，其方法如下：

result = 1
while b > 0
  if b is odd
    result *= a
    b -= 1
  b /= 2
  a = a * a

它通常是指数大小的对数。该算法基于不变式" a ^ b * result = a0 ^ b0"，其中a0和b0是a和b的初始值。

对于负或者非整数指数，需要对数和逼近以及数值分析。运行时间将取决于所使用的算法以及对该库进行调整的精度。

编辑：由于似乎有一些兴趣，这是一个没有多余乘法的版本。

result = 1
while b > 0
  while b is even
    a = a * a
    b = b / 2
  result = result * a
  b = b - 1

我有机会了解fdlibm的实现。注释描述了所使用的算法：

*                    n
 * Method:  Let x =  2   * (1+f)
 *      1. Compute and return log2(x) in two pieces:
 *              log2(x) = w1 + w2,
 *         where w1 has 53-24 = 29 bit trailing zeros.
 *      2. Perform y*log2(x) = n+y' by simulating muti-precision
 *         arithmetic, where |y'|<=0.5.
 *      3. Return x**y = 2**n*exp(y'*log2)

然后列出所有已处理的特殊情况(0、1，inf，nan)。

在进行所有特殊情况处理之后，代码中最紧张的部分涉及" log2"和" 2 **"计算。在这两个循环中都没有循环。因此，尽管浮点图元很复杂，但它看起来像一个渐近恒定时间算法。

欢迎浮点专家(我不是其中的一员)发表评论。 :-)

如果我正在编写针对Intel的pow函数，则将返回exp2(log2(x)* y)。英特尔的log2微代码无疑比任何我能编写的代码都要快，即使我还记得我一年级的微积分和研究生数值分析。

除非他们发现了更好的方法，否则我相信三角函数，对数函数和指数函数的近似值(例如，对于指数增长和衰减)通常使用算术规则和泰勒级数展开来计算，从而得出精确的近似结果达到要求的精度。 (有关幂级数，泰勒级数和Maclaurin系列函数展开的详细信息，请参阅任何微积分书。)请注意，距离我做这件事已经有一段时间了，例如，我无法告诉我们确切的计算方法我们需要包括的系列中的术语数量可确保误差足够小，以至于在双精度计算中可以忽略不计。

例如，针对e ^ x的Taylor / Maclaurin系列展开式是这样的：

+inf [ x^k ]           x^2    x^3      x^4        x^5
e^x = SUM  [ --- ] = 1 + x + --- + ----- + ------- + --------- + ....
      k=0  [  k! ]           2*1   3*2*1   4*3*2*1   5*4*3*2*1

如果采用所有项(k从0到无穷大)，则该扩展是精确且完整的(没有错误)。

但是，如果我们不把所有的项都带到无穷大，而是在说了5个或者50个项之后停了下来，那么我们得到的近似结果与实际e ^ x函数值的差值会很容易计算。

对于指数而言，好消息是它可以很好地收敛，并且多项式扩展的项很容易迭代编码，因此我们(重复，可能要记住，已经有一段时间了)甚至不需要预先计算所需的项数确保错误小于精度，因为我们可以在每次迭代中测试贡献的大小，并在该贡献足够接近零时停止。在实践中，我不知道该策略是否可行，所以我不得不尝试一下。我早已忘记了一些重要的细节。诸如：机器精度，机器误差和舍入误差等内容。

另外，请注意，如果我们不使用e ^ x，但是使用另一个基数(例如2 ^ x或者10 ^ x)进行增长/衰减，则近似多项式函数会发生变化。

我们可以使用exp(n * ln(x))计算xn。 x和n都可以是双精度浮点数。可以使用泰勒级数计算自然对数和指数函数。在这里我们可以找到公式：http://en.wikipedia.org/wiki/Taylor_series