FEE方式

数学において、FEE法、または高速E関数評価法は、特殊な形式の級数を高速に合計する方法です。この方法は、1990年にエカテリーナ・カラツバ^{[1] [2]によって構築され、}シーゲルE関数、特にの高速計算を可能にすることからこの名前が付けられました。 ${\displaystyle e^{x}}$

「指数関数に似た」関数のクラスは、カール・ルートヴィヒ・シーゲルによって「E関数」と名付けられました。^{[3]これらの関数の中には、}超幾何関数、円筒関数、球面関数など の特殊関数が含まれます。

FEE を使用すると、次の定理を証明することができます。

定理:を初等超越関数、つまり指数関数、 三角関数、初等代数関数、またはそれらの重ね合わせ、それらの逆関数、または逆関数の重ね合わせとします。 すると${\displaystyle y=f(x)}$

${\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}$

ここで、桁までの精度を持つ関数の計算の複雑さ (ビット)は、2 桁の整数の乗算の複雑さです。 ${\displaystyle s_{f}(n)}$${\displaystyle f(x)}$${\displaystyle n}$${\displaystyle M(n)}$${\displaystyle n}$

FEE 法に基づくアルゴリズムには、任意の引数の値に対する任意の基本超越関数、古典定数e、 オイラー定数、カタラン定数、アペリー定数^[4]、オイラーガンマ関数とその導関数、超幾何関数^[5]、球面関数、円筒関数 (ベッセルを含む) ^[6]などの高次超越関数、引数の代数値とパラメータに対するその他の関数 、引数の整数値に対するリーマンゼータ関数^{[7] [8]}、整数引数とパラメータの代数値に対するフルビッツゼータ関数^{[9] 、および}確率の積分、フレネル積分、積分指数関数、三角積分、および引数の代数値に対するその他の積分^[10]などの特殊積分 (これらの積分は、計算量の境界が最適なものに近い) を高速に計算するアルゴリズムが含まれます。 ${\displaystyle \pi,}$ ${\displaystyle \gamma ,}$

${\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}$

FEEは、高次超越関数のクラス^[11]、数理物理学の特定の特殊積分、オイラー定数、カタラン定数^[12]、アペリ定数などの古典的な定数の値を高速に計算することを可能にします。 FEE法のさらなる利点は、FEEに基づくアルゴリズムを並列化できることです。

定数を素早く評価するには、オイラーの公式を使い 、FEEを適用してテイラー級数を合計します。 ${\displaystyle \pi,}$${\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$

${\displaystyle \arctan {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},}$

${\displaystyle \arctan {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},}$

境界を満たす 残りの項${\displaystyle R_{1},}$ ${\displaystyle R_{2},}$

${\displaystyle |R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};}$

${\displaystyle |R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};}$

そして

${\displaystyle r=n,\,}$

${\displaystyle 4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.}$

FEEで計算するには 、他の近似値も使用できる^[13]すべてのケースで計算の複雑さは ${\displaystyle \pi }$

${\displaystyle s_{\pi }=O(M(n)\log ^{2}n).\,}$

オイラー定数ガンマを 桁精度で計算するには、2つの級数をFEEで足し合わせる必要があります。つまり、 ${\displaystyle n}$

${\displaystyle m=6n,\quad k=n,\quad k\geq 1,\,}$

${\displaystyle \gamma =-\log n\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!(r+1)}}+O(2^{-n}).}$

複雑さは

${\displaystyle s_{\gamma }=O(M(n)\log ^{2}n).\,}$

定数を素早く評価するために、 FEEを他の近似値に適用することが可能である。^[14]${\displaystyle \gamma }$

FEE によって、次の 2 つのシリーズが高速に計算されます。

${\displaystyle f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},}$

${\displaystyle f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},}$

が整数であるという仮定の下で、 ${\displaystyle a(j),\quad b(j)}$

${\displaystyle |a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K}$

と は定数であり、 は代数的数である。この級数の評価の複雑さは ${\displaystyle C}$${\displaystyle z}$

${\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,}$

${\displaystyle s_{f_{2}}(n)=O\left(M(n)\log n\right).}$

定数テイクの評価には、テイラー級数の項${\displaystyle e}$${\displaystyle m=2^{k},\quad k\geq 1}$${\displaystyle e,}$

${\displaystyle e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.}$

ここで を選択し、余りに対して不等式が満たされることを要求します。これは、例えば の場合に当てはまります。したがって、を取ると、 自然数は不等式によって決定されます。 ${\displaystyle m}$${\displaystyle R_{m}}$${\displaystyle R_{m}\leq 2^{-n-1}}$${\displaystyle m\geq {\frac {4n}{\log n}}.}$${\displaystyle m=2^{k}}$${\displaystyle k}$

${\displaystyle 2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.}$

合計を計算します

${\displaystyle S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},}$

以下のプロセスの手順 に従います。${\displaystyle k}$

ステップ1.加数をペアで順番に組み合わせて、括弧から「明らかな」共通因数を取り、 ${\displaystyle S}$

${\displaystyle {\begin{aligned}S&=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\cdots \\&={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\cdots .\end{aligned}}}$

括弧内の式の整数値のみを計算します。つまり、

${\displaystyle m,m-2,m-4,\dots .\,}$

したがって、最初のステップでは、合計は ${\displaystyle S}$

${\displaystyle S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),}$

${\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}$

最初のステップでは、次の形式の整数 ${\displaystyle {\frac {m}{2}}}$

${\displaystyle \alpha _{m_{1}-j}(1)=m-2j,\quad j=0,1,\dots ,m_{1}-1,}$

が計算されます。その後は、同様の方法で操作します。各ステップで合計の被加数をペアで順番に組み合わせ、括弧から「明らかな」共通因数を取り出し、括弧内の式の整数値のみを計算します。このプロセスの最初のステップが完了したと仮定します。 ${\displaystyle S}$${\displaystyle i}$

ステップ（）。 ${\displaystyle i+1}$${\displaystyle i+1\leq k}$

${\displaystyle S=S(i+1)=\sum _{j=0}^{m_{i+1}-1}{\frac {1}{(m-1-2^{i+1}j)!}}\alpha _{m_{i+1}-j}(i+1),}$

${\displaystyle m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},}$

我々は次の形式の整数 のみを計算する。${\displaystyle {\frac {m}{2^{i+1}}}}$

${\displaystyle \alpha _{m_{i+1}-j}(i+1)=\alpha _{m_{i}-2j}(i)+\alpha _{m_{i}-(2j+1)}(i){\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}},}$

${\displaystyle j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.}$

ここ

${\displaystyle {\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}}$

整数の積です。 ${\displaystyle 2^{i}}$

等。

ステップ、最後のステップ。 上で説明した高速アルゴリズムを使用して、1つの整数値を計算し、その整数を 桁 までの精度で1 回割ります 。得られた結果は、桁までの和または定数です。すべての計算の複雑さは、 ${\displaystyle k}$${\displaystyle \alpha _{1}(k),}$${\displaystyle (m-1)!,}$${\displaystyle \alpha _{1}(k)}$${\displaystyle (m-1)!,}$${\displaystyle n}$${\displaystyle S,}$${\displaystyle e}$${\displaystyle n}$

${\displaystyle O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).\,}$

• 高速アルゴリズム
• AGM方式
• 計算の複雑さ

• http://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm