エストリンの計画

数値解析において、エストリンのスキーム（ジェラルド・エストリンにちなんで名付けられた）は、エストリン法としても知られ、多項式の数値評価のためのアルゴリズムです。

多項式を評価するためのHorner 法は、この目的に最もよく使用されるアルゴリズムの 1 つであり、Estrin 法とは異なり、任意の多項式を評価するために必要な乗算と加算の回数を最小限に抑えるという意味で最適です。最新のプロセッサでは、互いの結果に依存しない命令は並列で実行できます。Horner 法には、それぞれが前の命令に依存する一連の乗算と加算が含まれているため、並列で実行できません。Estrin 法は、このシリアル化を克服しながらも、最適にかなり近い方法の 1 つです。

エストリンの方式は再帰的に動作し、xのn次多項式（n ≥ 2）を、 ⌈ n /2⌉の独立した演算（x ²を計算するために1つ追加）を使用してx ²の⌊ n /2 ⌋次多項式に変換します。

任意の多項式P ( x ) = C ₀ + C ₁ x + C ₂ x ² + C ₃ x ³ + ⋯ + C _n x ⁿが与えられた場合、隣接する項を ( A  +  Bx )の形式の部分式にグループ化し、それをx ²の多項式として書き直すことができます。P ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + ( C ₄ + C ₅ x ) x ⁴ + ⋯ = Q ( x ² )。

これらの各部分式とx ^{2 は}並列に計算できます。また、一部のアーキテクチャではネイティブの乗算累積命令を使用して評価することもできます。これは、Horner 法と共通する利点です。

このグループ化を繰り返すと、 x ⁴の多項式が得られます: P ( x ) = Q ( x ² ) = (( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² ) + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴ + ⋯ = R ( x ⁴ )。

これを⌊ log ₂ n ⌋ +1 回繰り返すと、多項式の並​​列評価のためのエストリンのスキームに到達します。

1. 0 ≤  i  ≤  ⌊ n /2 ⌋のすべての値について、 D _i = C _{2 i} + C _{2 i +1} xを計算します。( nが偶数の場合、C _{n +1}  = 0 となり、D _{n /2}  =  C _nとなります。)
2. n ≤ 1の場合 、計算は完了し、D ₀が最終的な答えになります。
3. それ以外の場合は、y = x ^{2を計算します（} D _iの計算と並行して）。
4. エストリンの方式を使用して、Q ( y ) = D ₀ + D ₁ y + D ₂ y ² + ⋯ + D _{⌊ n /2 ⌋} y ^{⌊ n /2 ⌋}を評価します。

これは、1 行目で合計n 回の乗算累積演算 (Horner 法と同じ) を実行し、3 行目で追加の⌊ log ₂ n ⌋ の二乗を実行します。これらの追加の二乗と引き換えに、スキームの各レベルのすべての演算は独立しており、並列に計算できます。最長の依存パスは、⌊ log ₂ n ⌋ +1 演算の長さです。

P _n ( x ) を次の形式のn次多項式とします: P _n ( x ) =  C ₀ + C ₁ x + C ₂ x ² + C ₃ x ³ + ⋯ + C _n x ⁿ

Estrin の方式で記述すると次のようになります。

P ₃ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ²

P ₄ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + C ₄ x ⁴

P ₅ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + ( C ₄ + C ₅ x ) x ⁴

P ₆ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + (( C ₄ + C ₅ x ) + C ₆ x ² ) x ⁴

P ₇ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴

P ₈ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴ + C ₈ x ⁸

P ₉ ( x ) = ( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴ + ( C ₈ + C ₉ x ) x ⁸

…

P ₁₅ ( x ) の評価を詳しく考えてみましょう。

入力: x、C ₀、C ₁、C ₂、C ₃、C ₄、C ₅ 、C _{6 、} C ₇、C ₈、C _{9 、} C ₁₀、C ₁₁、C ₁₂、C _{13 、} C ₁₄、C ₁₅

ステップ 1: x ²、C ₀ + C ₁ x、C ₂ + C ₃ x、C ₄ + C ₅ x、C ₆ + C ₇ x、C ₈ + C ₉ x、C ₁₀ + C ₁₁ x、C ₁₂ + C ₁₃ x、C ₁₄ + C ₁₅ x

ステップ 2: x ⁴、( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ²、( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ²、( C ₈ + C ₉ x ) + ( C ₁₀ + C ₁₁ x ) x ²、( C ₁₂ + C ₁₃ x ) + ( C ₁₄ + C ₁₅ x ) x ²

ステップ 3: x ⁸、(( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² ) + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴、(( C ₈ + C ₉ x ) + ( C ₁₀ + C ₁₁ x ) x ² ) + (( C ₁₂ + C ₁₃ x ) + ( C ₁₄ + C ₁₅ x ) x ² ) x ⁴

ステップ 4: ((( C ₀ + C ₁ x ) + ( C ₂ + C ₃ x ) x ² ) + (( C ₄ + C ₅ x ) + ( C ₆ + C ₇ x ) x ² ) x ⁴ ) + ((( C ₈ + C ₉ x ) + ( C ₁₀ + C ₁₁ x ) x ² ) + (( C ₁₂ + C ₁₃ x ) + ( C ₁₄ + C ₁₅ x ) x ² ) x ⁴ ) x ⁸

• Estrin, Gerald (1960 年 5 月)。「コンピュータ システムの構成 - 固定構造と可変構造のコンピュータ」(PDF)。Proc . Western Joint Comput. Conf。サンフランシスコ: 33–40。doi :10.1145/ 1460361.1460365。S2CID 16384320  。
• Muller, Jean-Michel (2005).初等関数: アルゴリズムと実装(第 2 版). Birkhäuser. p. 58. ISBN 0-8176-4372-9。

• fast_polynomial、改良されたスキームを使用する Sage ライブラリ (拡張概要)。