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

Question

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

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

Answer 1

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

\n\n

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

\n\n

\n\n

编辑

\n\n

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

\n\n

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

\n\n

\n\n

想法

\n\n

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

\n\n

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

\n\n

例如，迭代次数不变的循环可以像这样轻松扩展：

\n\n

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

是相同的：

\n\n

a *= a; a *= a; a *= a; a *= a; a *= a;\n