بستن پنجره
از نوشته‌ها خوشم اومد:
از این نوشته خوشم اومد:
تجربه‌های پراکنده‌ی یک مسعود
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.

محاسبه‌ی فاکتوریل اعداد بزرگ - تجربه‌های پراکنده‌ی یک مسعود
تجربه‌های پراکنده‌ی یک مسعود
115.005.00

چطور شاخ غول فاکتوریل را بشکنیم

چند روز پیش که با بچه‌ها نمونه سوالات ACM رو حل می‌کردیم، یه جایی به عدد 123456789 خوردیم و این سوال پیش اومد که می‌شه فاکتوریل این عدد رو حساب کرد؟

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

1  int fact_1(int n){
2    if(n < 2 )
3      return 1;
4    return n * fact_1(n - 1);
5  }

    این کد ساده‌ترین روش محاسبه‌ی فاکتوریل با زبان‌های خاندان C هست. یه روش دیگه هم به این ترتیب‌ه:

1  int fact_2(int n){
2    int fact = 1, i;
3    for(i = 2 ; i <= n ; i++)
4      fact *= i;
5    return fact;
6  }

    مزیت این تابع کنار گذاشتن فراخوانی بازگشتی‌ه که هم منبع بیشتری مصرف می‌شد و هم سرعت پایین‌تری داشت. اما این دو تابع یه ویژگی مشترک دارن: هیچ‌کدوم، مستقل از انتخاب int یا long یا long long به عنوان متغیر محاسباتی، قادر به محاسبه‌ی $12345!$ نیستن.

    بر اساس بحث بالا این سوال پیش می‌یاد که چطور می‌شه فاکتوریل اعداد بزرگ رو محاسبه کرد یا حداقل تخمین زد؟

    تخمین استرلینگ (تقریب استرلینگ - Stirling's approximation): بر اساس این تخمین مقدار $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 function): تابع گاما اینطور تعریف شده:

\[ \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! = 10 ^ {945335859.455415\cdots } = 10 ^ {0.455415\cdots} \times 10 ^ {945335859} \sim 2.85 \times 10^{945335859} \]

    پس $123456789!$ یه عدد $945335860$، حدود یک میلیارد، رقمی‌ه که برای ذخیره کردن عدد دقیق اون روی حافظه‌ی کامپیوتر به حدود سه گیگابیت، نزدیک چهارصد مگابایت، فضا نیاز داریم.


این نوشته آخرین بار در تاریخ جمعه، ۱۹ آذر ماه ۱۳۹۵ مورد بازبینی نگارشی قرار گرفته است.
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 

سوال:   دو دو  تا؟    (عدد) تا