执行取幂的最快算法是什么？

Question

执行取幂的最快算法是什么？为简单起见,我们假设自然数字基数和指数.

有效的数学库会使用什么？

(当我搜索它时,我得到的结果与指数时间内运行的算法有关.)

Answer 1

上述所有二进制方法的问题在于它们仅限于整数。如果“求幂”是指计算 e^x 函数，那么我见过的最好的方法是快速收敛的幂级数，以及在有限范围内有效的多项式、有理数或 Pade 近似。

有一点可以肯定：如果您找到一种将 e^x 精确到小数点后 96 位的快速算法，那么您也将找到一种更快的计算对数的方法（由 Newton-Raphson 提出）。事实上，Newton-Raphson 是二次收敛的，因此每次迭代时日志中的精度位数都会加倍。这是加州大学洛杉矶分校 (UCLA) 的内特·格罗斯曼 (Nate Grossman) 在 Forth 时代的最爱。

早在四元计算器时代，我曾经使用 e^x = (1+x/1024)^10。当然，对于 x 非常大或非常小的情况，这会失败，但你可以明白为什么它有效。如果你有一个平方根按钮，你可以颠倒这个想法来得到对数。但指数函数不需要平方根。

我想知道 AGM 算法是否有某种反演可以实现指数函数……嗯……

Answer 2

对于小指数，Python 使用二进制求幂（一种通过平方求幂的类型），如http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518的第 2874 行所示

对于较大的指数，它使用 2^5 进制求幂（另一种通过平方求幂的类型）。

如果您只关心结果的最高有效位，那么您可以非常快速地计算 x^y=exp(y*log(x))。

如果您只关心结果的最低有效数字（例如，对于编程竞赛），那么您可以计算以某个值 M 为模的指数。例如，Python 命令 pow(x,y,1000) 将计算最后 3 x 的 y 次方数字。它通过平方方法求幂来完成此操作，但请注意，这比计算完整结果要快得多，因为它确保中间数永远不会大于 M。

作为额外的改变（如果您只对最低有效数字感兴趣），您可以使用欧拉定理http://en.wikipedia.org/wiki/Euler%27s_theorem来减小指数的大小。