FEE 방식

수학에서 FEE 방법, 즉 빠른 E-함수 평가 방법은 특수형태의 시리즈를 빠르게 합산하는 방법이다.1990년 에카테리나 가라쓰바에^[1][2] 의해 건설되었으며, 특히 ${\$의 시겔 e-기능의 빠른 연산이 가능하게 해 붙여진 이름이다$.$

"지수함수와 비슷한" 기능 종류에는 칼 루드비히 시겔의 "E 기능"이라는 이름이 붙었다.^[3]이러한 기능들 중에는 초기하함수, 실린더, 구형함수 등과 같은 특별한 기능들이 있다.

FEE를 이용하면 다음과 같은 정리를 증명할 수 있다.

정리:$y{\displaystyle }$= ${\displaystyle f}$( ${\displaystyle x}$) ${\displaystyle y=f(x$)}을$($를) 기본 초월 함수, 즉 지수함수 또는 삼각함수, 또는 초등 대수함수, 그 중첩, 또는 그 역, 또는 인버스의 중첩이 되도록$$ 한다.그러면

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

$여기$서 $s{\displaystyle {}_{}}$ ${\displaystyle f_{}}$(${\displaystyle n}$) ${\displaystyle s_{f}(n)}$은(는)${\displaystyle \mathrm{함수}}$f ($$x ) {\$displaystyle f($x$$)}의 계산(비트) $복잡성$으로,$$최대 n {\$displaystyle$ $n$$}$자리수$$, $M{\displaystyle }$($n)$ ${\displaystystystyle n}$ 정수$$ 2개의 곱셈 복잡도 복잡도$$ 있다.

그 알고리즘을 수행 법 FEE에 기초한 인수의 값이{\displaystyle \gamma,}스페인과 Apéry 그런 높은 초월 기능 constants,[4]어떤 초등 transcendental 기능 고전적인 상수 eπ,{\displaystyle \pi,}은 오일러 상수 γ의 빠른 계산에 알고리즘을 포함한다.로논쟁의 대수적 가치와 매개 변수의 오일러 감마 함수와 미분형, hypergeometric,[5]구형 실린더(는 베셀 포함)[6]기능과 다른 역할, 리만 제타 함수에 정수 값의 argument[7][8]와 후르 비츠의 제타 함수에 정수 주장과 대수적 가치의 페이지의 주한 arameter,[9]또한 확률의 적분, 프레스넬 적분, 적분 지수함수, 삼각적 적분, 그리고 최적의 적분, 즉 복잡성에 가까운 인수의 대수적 값에 대한 일부 다른 적분들과^[10] 같은 특별한 통합들.

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

현재는 FEE만이 상위 초월함수의 종류,^[11] 수학물리학의 특정 특수집적 및 오일러, 카탈로니아^[12], 아페리의 상수와 같은 고전 상수로부터 기능의 값을 빠르게 계산할 수 있게 한다.^[when?]FEE 방법의 또 다른 장점은 FEE를 기반으로 알고리즘을 병렬화할 수 있다는 것이다.

고전 상수의 FEI 연산

For fast evaluation of the constant ${\displaystyle \pi ,}$ one can use the Euler formula ${\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$ and apply the FEE to sum the Taylor series for

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

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

경계를$$ ${\displaystyle {충족}_{}}$하는${\displaystyle {}_{}}$나머지$$용어 R 1, {\$displaystyle$R_{${\displaystyle 1_{}}$},} R 2, {\$displaystyle R_{2}.$

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

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

그리고 위하여

$r=n,\,}$

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

FREE로 $calculate$ ${\displaystyle \pi }$을(를) 계산하려면 다른 근사치도^[13] 사용할 수 있음 모든 경우에 복잡성은 다음과 같다.

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

$최대{\displaystyle }$ n {\$displaystyle$ n$}$자리까지의$$ 정확도로 $오일러$ 상수 감마를 계산하려면 FEE 2 시리즈를 합해야 한다$.$즉, 을 위해

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

${\displaystyle \cHB =-\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}:{(r+1){{(r+1)}+O(2^{-n}).}$

복잡성은

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

상수 $\gamma {\displaystyle }$ ${\displaystyle \gamma}$을(를) 빠르게 평가하려면 FREE를 다른 근사치에 적용하는 것이 가능하다$$.^[14]

특정 전력 시리즈의 FEE 연산

FEE에 의해 다음 두 개의 시리즈가 빠르게 계산된다.

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

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

$a{\displaystyle }$( ${\displaystyle j}$)${\displaystyle }$, ${\displaystyle b}$( j${\displaystyle }$) ${\displaystyle a(j)},\displayby$ b$(j)}$이(가) 정수라는$$ 가정 하에,

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

및 $C{\displaystyle }$ ${\displaystyle C}$은(는) 상수이고, $z{\displaystyle }$ ${\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).}$

고전 상수 e의 FEE 계산

상수 $e{\displaystyle }$ ${\displaystyle e}$의 $평가$는 m${\displaystyle }$= ${\displaystyle {2k}^{}}$ ${\displaystyle k}$ ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle m=2^{k},\quad k\geq 1$ $e{\displaystyle }$ ,${\displaystyle$ e$,}$에 대한 Taylor 시리즈의 항을 취한다$$.

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

여기서는 $나머지{\displaystyle }$ ${\displaystyle R_{}}$ $m{\displaystyle {}_{}}$ ${\$에 대해$$ 불평등 R ${\displaystyle m_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{}}^{}}$- ${\displaystyle {\mathrm{n}}^{}}$- 1 ${\$이 충족되도록$$ m ${\displaystystyle m}$을(를) 선택한다$.$예를 들어 m${\displaystyle }m{\displaystyle }$ ${\displaystyle \frac{\mathrm{4n}}{}}$ ${\displaystyle \frac{\log \mathrm{logn}}{}}$ .${\displaystyle m\geq {\frac {4n}{\logn}}}}$ $따라서$ m = 2k$${\$displaystyle$m=$2^{k}}}}}$를 $자연수{\displaystyle }$ k = ${\displaystyle {2k}^{}}$ ${\displaystystyle k}$의 불평등에 의해 결정된다$$.

${\displaystyle 2^{k}\geq {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 ${\displaystyle k}$단계에서$$

1단계. $S{\displaystyle }$ ${\displaystyle S}$에서 합계를 순차적으로 대괄호에서 "확실한" 공통 인자를 구한다.

${\displaystyle {\reasoned}S&=\왼쪽({\frac {1}{(m-1)!}}}+{\frac{1}{(m-2)!}}}\오른쪽)+\왼쪽 \frac{1}{(m-3)!}}}{\frac{1}{(m-4)!}}}\오른쪽)+\cdots \\&={\frac {1}{(m-1)!2}}(1+m-1)+{\frac {1}{(m-3)!2}}(1+m-3)+\cdots .\end{aigned}}$

우리는 괄호 안에 있는 표현들의 정수 값, 즉 그 값만을 계산한다.

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

따라서$$ 첫 번째 단계에서 $S{\displaystyle }$ ${\displaystyle$ S$}$은(는)

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

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

첫 번째 단계 ${\displaystyle \frac{\mathrm{m}}{}}$ 2 ${\$개의 양식 정수$$

${\displaystyle \cHB_{1}-j}(1)=m-2j,\cHB=0,1,\cHB,m_{1}-1,}$

계산하다그 후에 우리는 비슷한 방식으로 행동한다: 각 단계에서 $[\displaystyle S}$의 합계를 쌍으로 순차적으로$$ 결합하면, 우리는 괄호에서 '관측적인' 공통 인자를 꺼내어 괄호 안에 있는 식들의 정수 값만 계산한다.이 프로세스의 첫 $번째{\displaystyle }$ i ${\displaystyle i}$ 단계가$$ 완료되었다고 가정하십시오.

단계 $i{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle$ i$+1}($${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle \le }$ ${\displaystyle k}$ ${\displaystyle i+1\leq$ k$}).$

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

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

우리는 폼의 $m{\displaystyle \frac{}{}}$ ${\displaystyle \frac{{\mathrm{}}^{}}{}}$ ${\displaystyle \frac{i^{}}{}}$+ ${\displaystyle \frac{1^{}}{}}$ ${\$정수만$$ 계산한다.

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

${\displaystyle j=0,1,\cHB,\propertym_{i+1}-1,\properties m=2^{k},\put k\geq i+1.}$

여기

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

${\displaystyle 2^{}}$ i ${\$ 2$^{i}$ 정수의$$ 제품이다.

등

마지막 $단계인$k ${\displaystyle$ k$}.$We compute one integer value ${\displaystyle \alpha _{1}(k),}$ we compute, using the fast algorithm described above the value ${\displaystyle (m-1)!,}$ and make one division of the integer ${\displaystyle \alpha _{1}(k)}$ by the integer ${\displaystyle (m-1)!,}$ wit$최대{\displaystyle }$ n ${\displaystyle n}$자리까지의$$ 정확도.$얻은{\displaystyle }$ 결과는 S ,${\displaystyle S,}$ 또는$$ 상수 $e{\displaystyle }$ ${\displaystyle$ e$}$을(를) $n$ ${\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