Hornerの方法(C言語によるはじめてのアルゴリズム入門)

Hornerの方法
多項式の値を求める。
$f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$
を次のように変換できる

$f(x) = (\dots ((( a_n x + a_{n-1}) x + a_{n-2}) x + a_{n-3})x \dots a_1)x +a_0$

以下は、
$f(x) = 5 x^4 + 4 x^3 + 3 x^2 + 2x + 1$ の場合

#-*- coding:utf-8 -*-
#Hornerの方法

def main():
	a = [1., 2., 3., 4., 5.]
	for x in xrange(1,6):
		print "fn(%f) = %f"%(x, fn(x, a, 4))

def fn(x, a, n):
	p = a[n]
	for i in reversed(xrange(0,n)):
		p = p * x + a[i]
	return p
	
if __name__ == "__main__":
	main()