روش FEE

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

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

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

قضیه: فرض می‌کنیم که اگر  یک تابع استعلایی مقدماتی باشد، یعنی تابع نمایی باشد یا یک تابع مثلثاتی، یا یک تابع جبری ابتدایی، یا برهم نهی آنها، یا معکوس آنها، یا برهم نهی معکوس‌ها. و بعد داریم:

 

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

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

 

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

FEE-محاسبه ثابت‌های کلاسیک 
می‌توان از فرمول اویلر به صورت زیر برای سنجش فوری و سریع ثابت   استفاده نمود  و مطابق بخش پایین می‌توان از FEE برای محاسبه محموع جملات تیلور استفاده کرد.

 

 

 

 

و برای

 

 

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

 

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

 

 

 

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

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

 

 

فرض می‌کنیم که  اعدادی صحیح هستند

 

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

جزئیات FEE در مثال محاسبه سریع ثابت کلاسیک e 
برای ارزیابی ثابت  گرفتن  ، شرایط سری تیلور برای 

 

ما در اینجا m را طوری انتخاب می‌کنیم که نیاز آن به باقی مانده  به طوریکه نابرابری مقابل را داشته باشیم  برطرف می‌شود. برای مثال زمانی که  ، ما  را به طوری در نظر می‌گیریم که عدد طبیعی  توسط نامساوی‌ها مشخص می‌گردد و داریم:

 

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

 

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

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

 

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

 

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

 

 

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

 

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

 

 

 

 

 

و غیره.

قسمت آخر. عددی صحیح را حساب می‌نماییم  ما با استفاده از الگوریتم فوری که پیش تر بررسی شد، حساب می‌نماییم  و تقسیمی از عدد صحیح انجام دهید  توسط عدد صحیح  با دقت تا  ارقام نتیجه به دست آمده حاصل جمع است پیچیدگی همه محاسبات تا n رقم برابر  است یا ثابت .

جستارهای وابسته 
 الگوریتم‌های سریع
 روش AGM
 پیچیدگی محاسباتی

منابع

پیوند به بیرون 
 http://www.ccas.ru/personal/karatsuba/divcen.htm
 http://www.ccas.ru/personal/karatsuba/algen.htm
الگوریتم‌های محاسباتی رایانه
محاسبات عددی