指数是如何计算的? [英] How are exponents calculated?

问题描述

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

I'm trying to determine the asymptotic run-time of one of my algorithms, which uses exponents, but I'm not sure of how exponents are calculated programmatically.

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

I'm specifically looking for the pow() algorithm used for double-precision, floating point numbers.

推荐答案

我有机会研究了 fdlibm 的实现.评论描述了所使用的算法:

I've had a chance to look at fdlibm's implementation. The comments describe the algorithm used:

 *                    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).

followed by a listing of all the special cases handled (0, 1, inf, nan).

在所有特殊情况处理之后，代码中最密集的部分涉及log2 和2** 计算.并且其中任何一个都没有循环.因此，尽管浮点原语很复杂，但它看起来像是一种渐近恒定时间算法.

The most intense sections of the code, after all the special-case handling, involve the log2 and 2** calculations. And there are no loops in either of those. So, the complexity of floating-point primitives notwithstanding, it looks like a asymptotically constant-time algorithm.

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

Floating-point experts (of which I'm not one) are welcome to comment. :-)

这篇关于指数是如何计算的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！