روش FEE

در ریاضی، **روش FEE روشی سریع برای حمع بندی** سری‌های است که به یک فرم خاص هستند. در سال ۱۹۹۰ این روش توسط Ekaterina A. Karatsuba **و FEE** نامیده شد - **ارزیابی فوری E-function** - زیرا محاسبات سریع Siegel را انجام می‌دهد. E توابع ممکن است، مخصوصاً از **<math>e^x.</math>**.

سیگل گروهی از توابع را که «مانند تابع‌های نمایی» هستند، «تابع E» نامید. از جمله این توابع می‌توان به توابع خاص مثل تابع فوق هندسی، استوانه، توابع کروی و … اشاره کرد.

قضیه مقابل را با استفاده از FEE می‌توان اثبات نمود:

**قضیه**: فرض می‌کنیم که اگر y=f(x) یک **[[تابع غیرجبری|تابع استعلایی]] مقدماتی** باشد، یعنی تابع نمایی باشد یا یک تابع مثلثاتی، یا یک تابع جبری ابتدایی، یا برهم نهی آنها، یا معکوس آنها، یا برهم نهی معکوس‌ها. و بعد داریم:

: 
s_f(n) = O(M(n)\log^2n). \,


در فرمول فوق: پیچیدگی محاسبه (bit) تابع s_f(n)  است  f(x) باn رقم دقت، پیچیدگی ضرب دو M(n)  است اعداد صحیح n رقمی

الگوریتم‌های که اساس آنها مبتنی بر روش FEE هستند روشی برای محاسبه فوری هر تابع ابتدایی ماورایی برای هر مقدار آرگومان، ثوابت کلاسیک e. <math>\pi,</math> اویلرر \gamma, کاتالان و آپری، توابع ماورایی بالاتر مثل تابع گامای اویلر و مشتقات آن، توابع ابر هندسی، توابع کروی، توابع استوانه ای و برخی از تابع‌های دیگر برای مقادیر جبری آرگومان و پارامترها، تابع زتای ریمان برای مقدارهای صحیح آرگومان و تابع زتای هورویتز برای آرگومان عدد صحیح و مقدارهای جبری پارامتر، و به شکل مشابهی انتگرال‌های ویژه ای نظیر انتگرال احتمال، انتگرال فرنل، تابع نمای  انتگرال، و برخی از انتگرال‌های دیگر برای مقدارهای جبری استدلال با حد بالای پیچیدگی که به حد بهینه نزدیک است شامل می‌شوند، پس داریم:

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


الان، تنها هزینه ایجاد می‌کند به محاسبه فوری مقدارهای توابع از گروهی از توابع برتر بالاتر، برخی انتگرال خاص از فیزیک و ریاضی از جمله ثابت کلاسیک به عنوان ثابت اویلرو ثابت کاتالان است و ثابت Apery کوتاه است. امکان موازی سازی الگوریتم‌ها بر اساس FEE است مزیت اضافی روش FEE.

## FEE-محاسبه ثابت‌های کلاسیک
می‌توان از فرمول اویلر به صورت زیر برای سنجش فوری و سریع ثابت \pi,  استفاده نمود \frac{\pi}{4} = \arctan \frac12 + \arctan \frac13, و مطابق بخش پایین می‌توان از FEE برای محاسبه محموع جملات تیلور استفاده کرد.

: 
\arctan \frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \cdots +
\frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1 ,


: 
\arctan \frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \cdots +
\frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2 ,


: |R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}}; 

: |R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};

و برای

: r = n,\,

: 4(|R_1|+|R_2|) \ 

می‌توان از سایر تقریب‌ها برای حساب کردن \pi توسط FEE نیز استفاده کرد با این حال درتمام حالات برای پیچیدگی داریم:

: s_\pi = O(M(n)\log^2 n). \,

برای حساب کردن گامای ثابت اویلر با n رقم دقت، باید با دو سری FEE جمع شوند. پس داریم:

: m=6n, \quad k = n, \quad k \geq 1, \, 

: 
\gamma = -
\log n \sum_{r=0}^{12n}
\frac{(-1)^rn^{r+1}}{(r+1)!} +
\sum_{r=0}^{12n}
\frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} +
O(2^{-n}) .


: s_\gamma = O(M(n)\log^2 n). \, 

برای بررسی فوری و سریع ثابت \gamma برای سایر تقریب‌ها امکان اعمال FEE وجود دارد.

## FEE-محاسبه سری‌های توان خاص
می‌توان دو سری زیر را با استفاده از FEE سریع حساب کرد پس داریم:

:  f_1 =
f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j, 

: f_2 = f_2(z) =
\sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!}, 

فرض می‌کنیم که a(j), \quad b(j) اعدادی صحیح هستند

: |a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ 

و C ثابت هستند و z عددی جبری است و برای پیچیدگی ارزیابی آن داریم:

: 
s_{f_1}(n) = O\left(M(n)\log^2n \right), \,


: 
s_{f_2}(n)=
O\left(M(n)\log n \right).


## جزئیات FEE در مثال محاسبه سریع ثابت کلاسیک e
برای ارزیابی ثابت e گرفتن m = 2^k, \quad k \geq
1 ، شرایط سری تیلور برای e,

: 
e = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} + R_m.


ما در اینجا m را طوری انتخاب می‌کنیم که نیاز آن به باقی مانده R_m به طوریکه نابرابری مقابل را داشته باشیم R_m \leq 2^{-n-1} برطرف می‌شود. برای مثال زمانی که m\geq \frac{4n}{\log n}. ، ما m=2^k را به طوری در نظر می‌گیریم که عدد طبیعی k توسط نامساوی‌ها مشخص می‌گردد و داریم:

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


جمع را محاسبه می‌کنیم

: 
S = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} =
\sum_{j=0}^{m-1}\frac{1}{(m-1-j)!} ,


و در k مرحله فرایند زیر داریم:

مرحله ۱. ترکیب در S مجموع‌ها را به صورت دوتایی از داخل پرانتز عامل مشترک «بدیهی» را انجام می‌دهیم و حساب می‌کنیم پس داریم:

: 
\begin{align}
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{align}


ما مقداری‌های صحیح عبارت‌های داخل پرانتز را حساب می‌کنیم، یعنی داریم:

: 
m , m-2, m-4, \dots . \,


پس، در مرحله اول مجموع S در است

: 
S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1), 

:  m_1 = \frac m2, m = 2^k, k \geq 1 .

در اولین قدم \frac m2 اعداد صحیح فرم

: 
\alpha_{m_1-j}(1) = m-2j, \quad j = 0, 1, \dots, m_1 - 1 ,


حساب می‌گردند. بعد از آن به روشی مانند آن عمل می‌نماییم: در هر مرحله مجموع جمع را به صورت جفت و متوالی ترکیب می‌کنیم S، فاکتور مشترک «بدیهی» را از براکت‌ها خارج می‌نماییم و فقط مقدارهای صحیح عبارات داخل پرانتز را محاسبه می‌کنیم. فرض کنید که اولی i مراحل این فرایند تکمیل شده‌است.

: 
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) ,

:  m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} ,


: 
\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)!}
,

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

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

و غیره.

قسمت آخر. عددی صحیح را حساب می‌نماییم \alpha_1(k), ما با استفاده از الگوریتم فوری که پیش تر بررسی شد، حساب می‌نماییم (m-1)!, و تقسیمی از عدد صحیح انجام دهید \alpha_1(k) توسط عدد صحیح (m-1)!, با دقت تا n ارقام نتیجه به دست آمده حاصل جمع است پیچیدگی همه محاسبات تا n رقم برابر S, است یا ثابت e.

: 
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
رده:الگوریتم‌های محاسباتی رایانه
رده:محاسبات عددی