Hornerの公式

Hornerの公式という多項式の計算を高速に行う方法があります。
と言っても仕組みは簡単で以下のような式変形を行うだけです。

f:id:inarizuuuushi:20170721133458p:plain:w600

単純に項ごとを足し合わせるよりも、掛け算の回数が減っていることが分かりますね。
計算量はそれぞれ
f:id:inarizuuuushi:20170721133553p:plain:w300
となっています。

実験

# P(x)
y = 0
for i in range(n):
    y = y + a[i]*(x**i)

# Horner_P(x)
z = 0
for i in range(n):
    z = a[i] + z*y


a_iは全て1(ノートPCで計測)

n x 計測時間(P(x))(s) 計測時間(Horner_P(x))(s)
10000 3 0.1968 0.0078
100000 3 77.75 0.4575


演算回数を減らすことがどれほど計算時間短縮につながるかが実感できますね。