ما معمولا برای توضیح رشد با سرعت زیاد از عبارت «رشد نمایی» استفاده میکنیم. رشد نمایی یعنی هر گام که پیش میرویم، از گام $n$ به گام $n + 1$، اندازه دو یا هر چند برابری میشود که به آن پایه یا مبنای رشد گفته میشود. این پایه همیشه ثابت است؛ یعنی چه مرحله اول باشیم و چه مرحله هزارم، همیشه مرحله بعدی ضرب در عدد ثابتی میشود. در حالت کلی میتوان نوشت:
\[ f(n ) = b \times f(n - 1 ),\; f(0) = c \]
که منظور از b همان پایه رشد است. مثلا اگر $b = 2$ باشد و $f(0 ) = 1$، به تابع $f(n) = 2^n$ میرسیم. این تعریف را با تعریف فاکتوریل مقایسه کنید:
\[ n! = n \times (n - 1 )!, \; 0! = 1 \]
از این تعریف مشخص است که رشد هر مرحله به مقدار خود $n$ بستگی دارد. یعنی مثلا مرحله دهم رشد ده برابر است و مرحله هزارم هزار برابر. پس میتوان حدس زد که چرا یک ماشینحساب ممکن است بتواند $ 2 ^{12345} $ را حساب کند و $12345!$ را هرگز!
زمانی که میخواهیم یادگیری برنامهنویسی را شروع کنیم معمولا یکی از تمرینات این است: «تابعی بنویسید که با دریافت عدد n، فاکتوریل آن را محاسبه کرده و بازگرداند». اگر نیت یادگیری توابع بازگشتی باشد کد به این ترتیب خواهد بود:
int fact_1(int n){
if(n < 2 )
return 1;
return n * fact_1(n - 1);
}
این کد سادهترین روش محاسبه فاکتوریل با زبانهای خاندان C است. یک روش دیگر هم به این ترتیب است:
int fact_2(int n){
int fact = 1, i;
for(i = 2 ; i <= n ; i++)
fact *= i;
return fact;
}
مزیت این تابع کنار گذاشتن فراخوانی بازگشتی است که هم منبع بیشتری مصرف میشد و هم سرعت پایینتری داشت. اما این دو تابع یک ویژگی مشترک دارند: هیچکدام، مستقل از انتخاب int یا long long به عنوان متغیر محاسباتی، قادر به محاسبه $12345!$ نیستند.
بر اساس بحث بالا این سوال پیش میآید که چطور میتوان فاکتوریل اعداد بزرگ را محاسبه کرد یا حداقل تخمین زد؟ برای محاسبه دقیق این اعداد بسیار بزرگ کلاسها و امکاناتی در هر زبان ممکن است وجود داشته باشد که کار را آسانتر میکنند. اما اگر n بسیار بزرگ باشد یا نیاز نداشته باشیم عدد دقیق فاکتوریل آن را بدانیم و صرفا تخمین آن در زمان کوتاه مد نظر باشد، چه راهکاری وجود دارد؟
[برگرد بالا]
بر اساس این تخمین مقدار $n!$ برای $n$ـهای به اندازه کافی بزرگ نزدیک به رابطه زیر است:
\[ n! \sim \sqrt{2n\pi}{(\frac{n}{e})}^n \]
مثلا برای $n = 20$:
\[ 20! = 2432902008176640000 \sim \sqrt{40\pi}{(\frac{20}{e})}^{20} \sim 2422786846761133394 \]
هرچقدر مقدار $n$ بزرگتر باشد، دقت محاسبه این رابطه هم بیشتر میشود. اما مشکل اینجاست که بخش $ {(\frac{n}{e})}^n $ خود عدد بزرگی است. در واقع اگر قدرت محاسبه چنین عدد بزرگی را داشتیم، خیلی راحت میشد خود $n!$ را نیز حساب کرد. تفاوت $n!$ و این عدد در ضرب $ \sqrt{2n\pi} $ است که چندان تفاوت چشمگیری در مقایسه با بزرگی خود اعداد نیست.
[برگرد بالا]
تابع گاما اینطور تعریف میشود:
\[ \Gamma(x) = \int_0^{\infty}t^{x-1}e^{-t}dt \]
ثابت میشود در تابع گاما اگر $x$ عدد طبیعی باشد، $ \Gamma(x) $ همان $(x-1)!$ هست. از طریق این تعریف میتوان درستی تخمین استرلینگ را نیز ثابت کرد. نکته جالب دیگر آن است که با استفاده از تابع گاما میتوان فاکتوریل برای اعداد حقیقی غیرصحیح نیز تعریف کرد. مثلا $ \Gamma(3.5) \sim 3.23 $ را میتوان $ 2.5!$ در نظر گرفت که بین $2!$ و $3!$ است.
محاسبه انتگرال معین با کامپیوتر، به ویژه وقتی حدود بینهایت داشته باشد، بحث خودش رو میطلبد. سوای این موضوع، این تابع هم مشکل تخمین استرلینگ را دارد و زمانی که قصد محاسبه این انتگرال به ازای اعداد بزرگ را داریم، با اعداد بسیار بسیار بسیار بزرگ روبرو میشویم که همان مقدار فاکتوریل است.
[برگرد بالا]
تخمین استرلینگ و تابع گاما کاربردهای خاص خودشان را در مباحث ریاضی و مهندسی دارند. ما برای محاسبه یا تخمین مقدار فاکتوریل اعداد بزرگ باید بتوانیم این عدد را به نحوی به بخشهای کوچکتر بشکنیم. اگر از طرفین تعریف فاکتوریل لگاریتم بگیریم به نتیجه زیر میرسیم:
\[ log \; n! = log \; \Pi_{i=1}^{n} \; i = \Sigma_{i=1}^{n} log \; i \]
یعنی:
\[ n! = 10 ^{\Sigma_{i=1}^{n} log \; i} \]
این رابطه محاسبه حاصلضرب اعداد یک تا $n$ را به محاسبه حاصلجمع لگاریتم اعداد یک تا $n$ تبدیل میکند. محاسبه این حاصلجمع با یک حلقه for ساده انجام میگیرد و در مقایسه با خود فاکتوریل عدد بسیار کوچکتری است. به عنوان نمونه:
\[ 12345! = 10 ^ {45150.537018\cdots } = 10^{0.537018\cdots} \times 10^{45150} \sim 3.44 \times 10^{45150} \]
این روش به ازای هر $n$ جواب دقیق میدهد و تنها به خاطر قطع بخش اعشاری در محاسبه لگاریتم محاسبه دچار خطا میشود.
به عنوان یک نمونه دیگر مقدار فاکتوریل را برای عدد 123456789 با این روش تخمین میزنیم:
\[ 123456789! = 10 ^ {945335859.455415\cdots } = 10 ^ {0.455415\cdots} \times 10 ^ {945335859} \sim 2.85 \times 10^{945335859} \]
این محاسبه نشان میدهد $123456789!$ یک عدد $945335860$، حدود یک میلیارد، رقمی است که برای ذخیره کردن عدد دقیق آن روی حافظه کامپیوتر به حدود سه گیگابیت، نزدیک چهارصد مگابایت، فضا نیاز داریم.
جمعبندی و نکات تکمیلی
در ادامه جمعبندی نوشتههای فوق به همراه برخی نکات تکمیلی و مفید آمده است.
[برگرد بالا]چون در فاکتوریل، هر مرحله ضرب بزرگتر از مرحله قبل میشود و این رشد بسیار سریعتر از رشد نمایی عادی است. بههمین دلیل مقدار فاکتوریل خیلی زود از محدوده اعدادی که در متغیرهای معمولی جا میشوند خارج میشود.
[برگرد بالا]در توانها، پایه ثابت است و فقط تعداد تکرار ضرب زیاد میشود. اما در فاکتوریل، هر مرحله باید در عددی بزرگتر از مرحله قبل ضرب شود. این موضوع باعث میشود فاکتوریل خیلی زودتر از توانها به اعدادی برسد که عملاً قابل محاسبه و ذخیرهسازی نیستند.
[برگرد بالا]روش بازگشتی خوانایی بیشتری دارد اما حافظه و زمان بیشتری مصرف میکند. روش حلقه کارآمدتر است. با این حال، هیچکدام از این دو روش برای فاکتوریلهای عظیم کاربرد ندارند، چون نوع دادهها اجازه ذخیره اعداد بزرگ را نمیدهند.
[برگرد بالا]تخمین استرلینگ یک روش مشهور برای تقریب زدن فاکتوریلهای بزرگ است. این روش مقدار تقریبی بسیار خوبی ارائه میدهد، مخصوصاً برای عددهای خیلی بزرگ. هرچند حتی در این روش هم با اعداد بزرگی روبهرو هستیم که ممکن است محاسبه آنها در عمل ساده نباشد.
[برگرد بالا]بله. با استفاده از تابعی به نام «گاما» میتوان برای عددهای غیرصحیح هم چیزی شبیه فاکتوریل تعریف کرد. این تابع در عددهای صحیح، همان فاکتوریل معمولی را تولید میکند و در عددهای غیرصحیح مقدارهای بین آنها را ارائه میدهد.
[برگرد بالا]کاربردیترین روش استفاده از «لگاریتم فاکتوریل» است. این روش ضربهای بزرگ را به جمعهای کوچک تبدیل میکند و در نتیجه امکان تخمین مقدار نهایی در زمان بسیار کم فراهم میشود.
[برگرد بالا]بله. این روش تقریباً مقدار دقیق به دست میدهد و تنها خطای آن از گرد کردن اعداد اعشاری بهوجود میآید. برای محاسبات مهندسی، علمی یا بررسی مرتبه رشد، این روش کاملاً قابل اعتماد است.
[برگرد بالا]در روش لگاریتمی ابتدا اندازه کلی عدد به دست میآید و از روی آن میتوان تعداد رقمهای فاکتوریل را تعیین کرد. به این ترتیب، حتی اگر خود عدد قابل ذخیرهسازی نباشد، میتوان فهمید چند رقم دارد.
[برگرد بالا]به ازای هر رقم تقریباً یک بیت حافظه نیاز است. بنابراین اگر فاکتوریلی چند صد میلیون رقم داشته باشد، برای ذخیره کامل آن صدها مگابایت حافظه لازم است.
[برگرد بالا]برای این کار باید از کتابخانههایی استفاده کرد که توانایی کار با اعداد نامحدود یا بسیار بزرگ را دارند. برخی زبانها مثل پایتون این قابلیت را بهصورت پیشفرض دارند. در زبانهایی مثل C و C++ یا جاوا باید از کتابخانههای ویژه مثل GMP یا BigInteger استفاده کرد.