Hornerの公式
という多項式の計算を高速に行う方法があります。
と言っても仕組みは簡単で以下のような式変形を行うだけです。
単純に項ごとを足し合わせるよりも、掛け算の回数が減っていることが分かりますね。
計算量はそれぞれ
となっています。
実験
# 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 |
演算回数を減らすことがどれほど計算時間短縮につながるかが実感できますね。