python - python中最快的多项式计算

Question

我正在开展一个 build 牛顿盆地的旧项目，我正在努力使其尽可能快。我要加快速度的第一件事是如何在给定的复点 x0 处计算多项式函数。我想到了 4 种不同的方法来做到这一点，并使用 timeit 对其进行了测试。我使用的代码如下:

import timeit
import numpy as np
import random
from numpy import polyval

class Test(object):
    re = random.randint(-40000, 40000)/10000
    im = random.randint(-40000, 40000)/10000
    x0 = complex(re, im)
    coefs = np.array([48,8,4,-10,2,-3,1])
    flip_coefs = np.flip(coefs)

    def solve0():
        y = np.array([Test.coefs[i]*(Test.x0**i) for i in range(len(Test.coefs))]).sum()
        return y

    def solve1():
        y = 0
        for i in range(len(Test.coefs)):
            y += Test.coefs[i]*(Test.x0**i)
        return y

    def solve2():
        y = np.dot(Test.coefs,Test.x0**np.arange(len(Test.coefs)))
        return y

    def solve3():
        y = polyval(Test.flip_coefs, Test.x0)
        return y


Test.solve0()


if __name__ == '__main__':
    print(timeit.timeit('Test.solve0()', setup="from __main__ import Test", number=10000))
    print(timeit.timeit('Test.solve1()', setup="from __main__ import Test", number=10000))
    print(timeit.timeit('Test.solve2()', setup="from __main__ import Test", number=10000))
    print(timeit.timeit('Test.solve3()', setup="from __main__ import Test", number=10000))

问题是，我非常确定 numpy.polyval() 是最快的，但似乎在 Linux 上，np.dot(coefs,x**np .arange(len(coefs))) 的速度是两倍多，无论 x0 的值如何(我不知道在 Windows 和 MacOS 中是否相同)。这是我得到的输出示例:

0.1735437790002834
0.12607222800033924
0.0313361469998199
0.0796813930001008

这看起来很奇怪，因为 numpy.polyval() 是专门为求解多项式而构建的。所以，我的问题是:这里是否缺少一些东西(可能与我选择的系数有关)？有没有更快的方法来计算多项式？

Answer 1

检查 source code观察 numpy 的 polyval() 函数，您会发现这是一个纯粹的 Python 函数。 Numpy 使用 Horner 的方法进行多项式求值(并且有助于同时求值多个点，尽管这种情况不适用于此处)。

回答您关于评估费用的问题，我相信Horner's method从算法的角度来看是最佳的:它允许仅使用 n 次乘法和 n 加法来计算 n 次多项式，这与您的最快的方法 solve2()，其中乘法运算随输入大小按多项式缩放。就计算速度而言，我怀疑您的方法与 polyval() 函数相比性能的提高来自于这样一个事实:numpy 中的点积是用 C 实现的，并且在那个前面。

附录:对于该主题的全面概述，我强烈推荐 Knuth 的 The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd ed.) ，其中第485页的4.6.4节提到了这种情况。我相信霍纳的方法对于单个多项式评估来说是最佳的，但是如果要多次评估该多项式，那么如果允许预处理，则可能会获得进一步的加速。