math - 幂函数是否在恒定时间内运行？

Question

当我在 C# 中使用 Math.Pow(double x, double y) 或 C++ 中的 math.h pow-function 等幂函数时，这些函数会在恒定时间内运行吗？

我问的原因是因为我想知道 (1-t)^n*p0 + ... + t^(n) * pN 形式上的“预先计算的”贝塞尔函数是否可以在线性时间内运行，这可以那么比以控制点和 t 作为参数的 De Casteljaus 算法的实现要快。

Answer 1

我认为这些方法使用基于迭代的处理来获得结果，并且只有当两次迭代的值之间的差异低于给定的误差常数时才会停止。

有一些迭代方法可以非常快速地收敛到幂运算的结果......所以我认为它们接近恒定时间。

这个问题有很多很好的解释： Math.Pow() 如何在 .NET Framework 中实现？

编辑

我在http://math.stackexchange.com中找到了很多可以使用的好材料。

• 计算 e^x 到任意小数位数的最快方法？
• 如何使用标准计算器计算 e^x
• 如何计算非整数指数？
• 数值估计 a^b
• e^(-x) 的近似值

这个非常有趣，因为它解释了一种使用人类语言计算幂的方法：

• 如何使用定点计算幂

想法

我不是数学天才，但据我所知，所花费的时间很大程度上取决于您选择的值，而是取决于您想要的精确位数。我想说的是它取决于论点，但有一个最大值。

另外，为了支持这个理论，看看这个算法（由 Sun 实现）： http: //pastebin.com/LDjS5mAR。没有循环，只有 ifs。我认为这是因为实现它的人选择了他们想要的固定精度……然后扩展了保证该精度所需的所有迭代。

例如，一个迭代次数不变的循环可以很容易地展开，如下所示：

for (int it = 0; it < 5; it++)
    a *= a;

是相同的：

a *= a; a *= a; a *= a; a *= a; a *= a;