如何计算指数？

Question

我试图确定我的一个算法的渐近运行时间,它使用指数,但我不确定如何以编程方式计算指数.

我特意寻找用于双精度浮点数的pow()算法.

Answer 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**计算.其中任何一个都没有循环.因此,尽管浮点基元的复杂性,它看起来像渐近恒定时间算法.

我们欢迎浮点专家(我不是其中一位)发表评论.:-)