روش FEE

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

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

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

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

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

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

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

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

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

FEE-محاسبه ثابت‌های کلاسیک

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

$\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},$

$\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},$

$|R_{1}|\leq {\frac {4}{5}}{\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}|)\ <\ 2^{-n}.$

می‌توان از سایر تقریب‌ها برای حساب کردن $\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)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{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|\ <\ 1;\quad K$

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

$s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\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{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}}$

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

$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 {m}{2}},m=2^{k},k\geq 1.$

در اولین قدم ${\frac {m}{2}}$ اعداد صحیح فرم

$\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