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