ما معمولا برای توضیح رشد با سرعت زیاد از عبارت «رشد نمایی» استفاده می‌کنیم. رشد نمایی یعنی هر گام که پیش می‌رویم، از گام $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$، حدود یک میلیارد، رقمی است که برای ذخیره کردن عدد دقیق آن روی حافظه کامپیوتر به حدود سه گیگابیت، نزدیک چهارصد مگابایت، فضا نیاز داریم.