秦九韶算法简介

程序员专属-极客T恤

秦九韶算法是中国南宋时期的数学家秦九韶表述求解一元高次多项式的值的算法——正负开方术。它也可以配合牛顿法用来求解一元高次多项式的根。在西方被称作霍纳算法,但秦九韶的发现比霍纳要早很多。

秦九韶算法,用于多项式的计算,即对于一个 n 次多项式,至多做 n 次乘法和 n 次加法。

优点

即使在现代,利用计算机解决多项式的求值问题时,秦九韶算法依然是最优的算法。对于计算机程序算法而言,加法比乘法的计算效率要高很多,而做一次乘法运算所用的时间比作一次加法运算要长得多,所以此算法极大地缩短了 CPU 的运算时间。如:

缺点

算法必须适应具体的计算机结构。串行处理机习惯采用循环和迭代算法,这样可以缩短程序长度,节省程序所占的存储空间量,简化编程。但是这些算法往往不适合在多处理机并行,因为它会导致大量相关,反倒用直接解法更能揭示出足够多的并行性。

如:E = a+b*x + c*x*x +d*x*x*x利用秦九韶算法可得:

E=a+x(b+x(c+x*d))

这是在单处理机上执行的典型循环算法。共需要3个乘加循环6级运算。反倒是原始公式直接解法共需要3个处理器4级运算完成,其加速比及效率都远远大于3个乘加循环6级运算。

参考资料

  • 李学干《计算机系统结构》