c - 什么算法用于c中的pow（）函数

Question

#include<stdio.h>
#include<math.h>

int main() {
double n,p,ans;
while(scanf("%lf %lf",&n,&p)==2)
{
    ans=pow(p,(1/n));

    printf("%.0lf\n",ans);
}
return 0; 
 }

这里使用什么算法来查找 ans。这个 pow() 函数的复杂度是多少？

Answer 1

C99 标准的第 4.12.7.4 节对pow功能没有更多的说明，如下：

新思科技

#include <math.h>
double pow(double x, double y);
float powf(float x, float y);
long double powl(long double x, long double y);

描述

pow函数计算提高x到幂y。如果x是有限且负的并且y是有限且不是整数值，则会发生域错误。可能会发生范围错误。如果x为 0 且y为 0，则可能发生域错误。如果x为零且y小于零，则可能发生域错误或范围错误。

退货

pow函数返回 [提高x到幂y]。

请注意，没有提供有关函数复杂性的信息，并且对要使用的算法没有任何期望。这是因为在 C 的某些实现中，这些函数可能是处理器本机的，而在其他体系结构中，硬件不提供浮点处理。

但是，您可以假设复杂性并不比log、乘法和exp组合的复杂性差：

double pow(double x, double y) {
    return exp(log(x)*y);
}

在许多具有 FP 单元的平台上，以 e 为底的取幂、浮点乘法和自然对数都需要O(1)时间，因此pow也应该如此。

-edit2- 我不太确定 and 的复杂性exp，log但我认为实现使用泰勒近似和一堆查找表。那仍然会给O(1).

Answer 2

正如前面的答案所说，这是不可能的。

在 x86 上，您可以使用fyl2x计算 (y *log2(x)) 和f2xm1指令 [连同 +1.0]来实现它

fld1            1.0
fld             y
fld             x 
fyl2x                  // y * log2(x)
fadd                   // add 1.0
f2xm1                  // 2 ^ (x-1)

然后在不支持或很少支持浮点单元中的 exp/log 指令的处理器上，log 和 exp 可能会使用 seeries 方程计算，该方程可能需要 5-20 次迭代，具体取决于输入值和方程的好坏。

我认为在这种情况下复杂性仍然是 O(1)，但我相信我们可以想出它不会那样工作的场景。