FEE method

در ریاضی، روش FEE روشی سریع برای حمع بندی سری‌های است که به یک فرم خاص هستند. در سال 1990 این روش توسط 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 مرحله فرایند زیر داریم :

مرحله 1. ترکیب در $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

This article "FEE method" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:FEE method. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• روش FEE

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• FEE method in English