الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
محاسبه‌ی فاکتوریل اعداد بزرگ - الگوریتمستان
الگوریتمستان
  »  

محاسبه‌ی فاکتوریل اعداد بزرگ

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

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

  

تخمین استرلینگ (تقریب استرلینگ - 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 با این روش تخمین می‌زنیم:

\[ 123456789! = 10 ^ {945335859.455415\cdots } = 10 ^ {0.455415\cdots} \times 10 ^ {945335859} \sim 2.85 \times 10^{945335859} \]

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

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
برچسب‌ها
        #محاسبات ریاضی 
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

وبگاه:

متن پیام: *

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

 


• محمد
یکشنبه، ۷ خرداد ماه ۱۳۹۶، ساعت ۰۱:۰۵

سلام من نفهمیدم چجوری باید حساب کرد


• امیر
سه‌شنبه، ۲۴ مرداد ماه ۱۳۹۶، ساعت ۰۰:۱۸

خیلی مطلب مفیدی و جالبی بود06


• مهدی
سه‌شنبه، ۲۱ آذر ماه ۱۳۹۶، ساعت ۲۱:۳۷

141414141414


• مهدی
سه‌شنبه، ۲۱ آذر ماه ۱۳۹۶، ساعت ۲۱:۳۹

خیلی خوبهخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخخ14141401010303030302020707060608091010101112131314141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414


• مهدی
سه‌شنبه، ۲۱ آذر ماه ۱۳۹۶، ساعت ۲۱:۴۲

12121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121211111112121212121212121212121212121212121212121212


• مهدی
سه‌شنبه، ۲۱ آذر ماه ۱۳۹۶، ساعت ۲۱:۴۵

14141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414


• مهدی
سه‌شنبه، ۲۱ آذر ماه ۱۳۹۶، ساعت ۲۱:۴۶

141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414121414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414


• مهدی
چهارشنبه، ۲۲ آذر ماه ۱۳۹۶، ساعت ۲۱:۱۳

141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141412141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414


• مهدی
چهارشنبه، ۲۲ آذر ماه ۱۳۹۶، ساعت ۲۱:۱۶

0708091011121314060504030201


• حسام
شنبه، ۱۶ دی ماه ۱۳۹۶، ساعت ۲۳:۴۵

02070707070707070707070707070707071414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۱۰۸۴ روز
تعداد بازدید:  ۱۵۷۸۸ بازدید
تعداد امتیاز:  ۱۷ امتیاز
میانگین امتیاز:  ۳.۷۱  از  ۵.۰۰
»  بازی Lights Out و ریاضیات دوست داشتنی
        حل بازی Lights Out با ریاضیات دوست داشتنی
»  نکته‌ای در مورد کلاس‌ها و مجموعه‌ها در ++C
        بررسی روش تعریف کلاس برای قابلیت استفاده از ظرف‌های مجموعه (set و unordered_set) در زبان برنامه‌نویسی ++C
»  سوال Free Ticket
        راهنمای حل سوال Free ticket، از سوالات المپیاد ملی کامپیوتر هندوستان
»  sync_with_stdio در زبان ++C
        نکته‌ای در مورد کارایی عملیات ورودی و خروجی در زبان برنامه‌نویسی ++C و عملکرد تابع sync_with_stdio
»  نکته‌ای در محاسبه‌ی زمان اجرای کد
        در مورد تفاوت توابع clock و time در زبان برنامه‌نویسی ++C برای محاسبه‌ی زمان اجرای برنامه
»  ابزار VJudge
        معرفی وب‌سایت Virtual Judge برای برگزاری مجازی مسابقه‌ی برنامه‌نویسی به سبک مسابقات ACM-ICPC
»  هدر فایل bits/stdc++.h
        معرفی هدرفایل bits/stdc++.h برای کاهش زمان آماده شدن کد مسابقات برنامه‌نویسی
»  نکته‌ای از مسأله‌ی Graphical Editor
        استفاده از stringstream در حل سوالات مسابفات برنامه‌نویسی با زبان برنامه‌نویسی ++C
»  ابزار UVA Toolkit
        معرفی وب‌سایت UVA Toolkit برای کمک به حل سوالات برنامه‌نویسی UVA Online Judge
»  نکته‌ای از مسأله‌ی LC-Display
        نکته‌ای در باب روش ذخیره کردن ورودی یک مسأله
»  تابع popen
        روش اجرای برنامه‌ای دیگر داخل کد ++C و استفاده از خروجی آن
»  سینوس و کسینوس را قورت بده
        محاسبه‌ی جدولی سینوس و کسینوس زوایای مشهور
»  نکته‌ای در استفاده از map
        نکته‌ای در مورد استفاده از ساختمان داده‌ی map با مثالی به زبان برنامه‌نویسی ++C
»  بازی مین‌روب
        بازنشر یک یادداشت قدیمی