【多項式計算の最適化】ホーナー法と、並列処理に強い「エストリン法」の比較検証

多項式計算を効率化する方法でホーナー法が有名ですが、並列処理が可能な環境ではエストリン法(estrin-method)も効率化手法として使うことができます。
今回は、有名な「ホーナー法」と、現代のCPUアーキテクチャで真価を発揮する「エストリン法（Estrin’s scheme）」について、20次の多項式を用いたベンチマーク結果を交えて解説します。

1. ホーナー法（Horner’s method）の復習

多項式を計算する際、素朴に実装すると累乗の計算が重複し、計算量が増えてしまいます。これを効率化するのがホーナー法です。

一般的な多項式の形：
\[P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0\]
これを以下のように変形します：
\[P(x) = (\dots((a_nx + a_{n-1})x + a_{n-2})x + \dots + a_1)x + a_0\]
ただの式変形で「ただネストしただけじゃないの？」と思うかもしれませんが、元の式だと\(x^n\)でxのn乗 \(x^{n-1}\)ででxのn-1乗を計算し、全体で、n+(n-1)+ … + 2 + 1 = \( 1/2 *n * (n+1) \)回 xを掛け算しなければならず、これらの計算のたびに丸め操作や足し算を行う必要があります。しかし、この変形により、掛け算回数が n 回に圧縮されそれに加えて以下のようなメリットがあります。

メリット

計算量の最小化: 乗算と加算の回数がそれぞれ \(n\) 回になり、計算効率が非常に高いです。
FMA（Fused Multiply-Add）との相性: (a * x) + b の形が連続するため、現代のCPUが持つFMA命令をフル活用できます。

2. なぜ今、エストリン法（Estrin’s method）なのか

ホーナー法は非常に効率的ですが、弱点があります。それはデータ依存性です。前のステップの結果が決まらないと次の乗算ができないため、計算が「直列」に並んでしまいます。これに対し、エストリン法は多項式を木構造のように分割して計算します。

ホーナー法は前の計算が終わらないと次ができない

エストリン法なら並列化できる

理論の説明（分解の仕組み）

例えば4次の多項式の場合、以下のようにグループ化します。
\[P(x) = (a_4x + a_3)x^2 + (a_2x + a_1)\]
※実際には \(x, x^2, x^4 \dots\) といった累乗をあらかじめ計算し、それらを使って項を組み合わせていきます。
このように分解することで、以下のメリットが生まれます。

並列計算の活用: 各グループの計算を独立して行えるため、CPUの「スーパースカラ（命令レベルの並列性）」を活かして、複数の演算ユニットで同時に処理できます。
計算深度の短縮: ホーナー法の依存関係の長さが \(O(n)\) なのに対し、エストリン法は \(O(\log n)\) に短縮されます。

実用例：lnの近似計算

電卓の自然対数計算に利用したテイラー展開の式について、f64(doubleと同精度の浮動小数点数)の精度を担保するために必要な12次の式なら上記のように3つのブロックに分解する方法が使えます.

3. 実装とベンチマーク環境

今回はRustを用い、以下の20次の係数セットを使用して「素朴な実装」「ホーナー法（FMAあり）」「エストリン法（FMAあり）」の3種を比較しました。

// 20次の係数（21個）
// P(x) = 0.1 * x^20 -0.2 * x^19 + .... - 2.0 * x + 2.1
const COEFFS_20: [f64; 21] = [
    0.1, -0.2, 0.3, -0.4, 0.5, -0.6, 0.7, -0.8, 0.9, -1.0,
    1.1, -1.2, 1.3, -1.4, 1.5, -1.6, 1.7, -1.8, 1.9, -2.0, 2.1
];

4. ベンチマーク結果

20次の多項式を1万回計算させた結果がこちらです。

ただの掛け算と加算で実装した多項式計算と、ホーナー法を用いた方法、エストリン法を用いた方法について計算結果と速度のベンチマークをとった結果

手法	実行速度 (Duration)	horner法との速度比
naive (素朴)	240 ms程度	x0.75
horner-fma	180.0 ms程度	x1.00
estrin-fma	60,0 ms程度	x3.00

考察

結果は一目瞭然で、エストリン法がホーナー法よりも約3倍速いという結果になりました。
ホーナー法もFMAによって高速化されていますが、エストリン法はCPUの空いている演算ユニットを効率よく使い切るため、20次という高次の計算では圧倒的な差が生まれます。
また、計算結果の微差（浮動小数点の精度）についても、計算順序が変わるため、丸め誤差の影響もわずかに異なり、エストリン法の方が信頼できます。

5. 導入時の注意点：次数が少ない場合は？

今回の実験では20次で大きな効果が得られましたが、次数が少ない（12次など）場合は、逆にホーナー法の方が早いことがあります。

理由は以下の通りです。

エストリン法は \(x^2, x^4\) といった累乗を事前に準備するコストがかかる。
低次では並列化による恩恵よりも、オーバーヘッドが上回ってしまう。

実際のアプリケーションや対象に合わせて、選択するアルゴリズムを変える必要があります。

8次だとほぼ速度が変わらない

正確な計算結果は 540297097444054751175882.9 であるため、元の式に忠実な方法だと.. 5466となっており、信頼できるのは上から15桁目まで、Horner法だと、…548,estrin法だと、…547となっており、正確な値が…5475なので、estrin法の方は最後の桁まで信頼できます。

ホーナー法： 20回連続で加算・乗算を繰り返すため、誤差が累積しやすい。
エストリン法： 木構造で計算するため、誤差の累積（計算の深さ）が \(O(\log n)\) に抑えられる。

まとめ

ホーナー法: 逐次計算に強く、メモリやレジスタ消費が少ない。低〜中次数向け。
エストリン法: 並列計算に強く、現代のCPUパワーを最大限に引き出せる。高次数向け。

「数学的に計算回数が少ない手法」が、必ずしも「現代のハードウェアで最速」とは限らないのが、最適化の面白いところですね。用途に合わせて最適なアルゴリズムを選んでいきましょう。

ホーナー法実装例：【Rustで作る電卓】浮動小数点数の構造をハックして対数関数(log)を実装する #15
エストリン法を検討したが見送った例：【最適化編】ホーナー法を超えて：エストリン法による対数計算の並列化 #16

ここまで読んでいただきありがとうございます。

では、次の記事で。　lumenHero