Java Math.pow（a，b）时间复杂度

Java Math.pow（a，b）时间复杂度

@Blindy讨论了Java可以采用的 可能 方法

pow

。

首先，一般情况 不能 重复相乘。对于指数不是整数的一般情况，它将不起作用。（签名

pow

是

Math.pow(double, double)

！）

在OpenJDK 8代码库中，的本机代码实现

pow

可以通过两种方式工作：

• 的第一个实现

  e_pow.c

  使用幂级数。C注释中描述了该方法，如下所示：

  * 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.
  • 1. Perform y*log2(x) = n+y’ by simulating multi-precision
  • arithmetic, where |y’|<=0.5.
  • 1. Return xy = 2nexp(y’log2)

• 中的第二个实现

  w_pow.c

  是

  pow

  对标准C库提供的功能的包装。包装器处理边缘情况。

现在，标准C库可能使用特定于CPU的数学指令。如果确实如此，并且JDK构建（或运行时）选择了第二个实现1，那么Java也将使用这些指令。

但是无论哪种方式，我都看不到任何使用重复乘法的特殊情况代码的痕迹。您可以放心地假设它是

O(1)

。

---

1-我尚未研究如何/何时进行选择。