(বিগ মড) Big Mod Algorithm

বিগ মড (Big Mod)

বিগ মড কি এই বিষয় নিয়ে আলোচনা করব না । কারন এই বিষয় নিয়ে অনেক জায়গায় আলোচনা করা হয়েছে । এখানে কিভাবে বিগমোড রিকার্সিভলি কাজ করে সেটা দেখানো হবে । ধরা যাক 2¹⁰ mod 10 এর মান বের করতে হবে । বিগ মোড এ পাওয়ার কে ভাগ ভাগ করে মান বের করা হয় । তাহলে চিত্র টি হবে

চিত্র হতে দেখা যাচ্ছে যে পাওয়ার এর সর্বশেষ মান 1 এবং পাওয়ার 0 হলে 2⁰=1 যা রিকার্সিভ ফাংশনের বেস কেস । আমরা জানি রিকার্সিভ ফাংশন আসলে কাজ করে মেমোরির স্ট্যাক এর মাধ্যমে । প্রত্যেক বার যখন ভিন্ন মান এর ফাংশন কল করা হয় তখন স্ট্যাক এ পুশ হতে থাকে  এবং বেস কেস যখন কোন মান রিটার্ন করে তখন পপ হতে থাকে এবং প্রত্যেক বার পপ হওয়ার সময় সেই ফাংশনের মান অনুযায়ী রেজাল্ট রিটার্ন করে যা পরবর্তী ফাংশনের কাজে লাগে । নিচের বিগ মোড ফাংশনটির কাজ দেখলেই ভালোমত বোঝা যাবে ।

long long int bigmod(long long int x,long long int n,long long int m)
{
    long long  int y;
    if(n==0)
    {
        return 1;
    }
    else if(n%2==0)
    {
        y=bigmod(x,n/2,m);
        return ((y*y)%m);
    }
    else
    {
        return(((x%m)*bigmod(x,n-1,m))%m);
    }
}

চিত্র অনুযায়ী পাওয়ার এর মান 0 হলে 1 রিটার্ন করবে ।

    if(n==0)
    {
        return 1;
    }

পাওয়ার এর মান জোড় হলে পাওয়ার কে ২ দ্বারা ভাগ করে ভাঙ্গিয়ে ফেলবে যেমন ঃ 2¹⁰= 2⁵*2⁵ ।

 else if(n%2==0)
    {
        y=bigmod(x,n/2,m);
        return ((y*y)%m);
    }

y*y কারন 2⁵*2⁵ এর মান হল 2¹⁰ এর মান , 2²*2² এর মান হল 2⁴

পাওয়ার এর মান বিজোড় হলেও দুই ভাগে ভাগ করতে হবে । এক্ষেত্রে বিজোড় পাওয়ার থেকে ১ বিয়োগ করে যা আসবে তার সাথে বেস ( এখানে ২) কে গুন করতে হবে । যেমন ঃ 2⁵= 2⁴*2¹

else
{
        return(((x%m)*bigmod(x,n-1,m))%m);
 }

লজিক বোঝার পর রিকার্সন বুঝতে পারলেই কাজ শেষ । প্রথম থেকে শুরু করি। এখানে

x=2 , n=10 , m=10

এখন বিগ মোড এর ফাংশন এ এই মানগুলো পাঠালে প্রথমে n=10 যা জোড় তাই

               y=bigmod(x,n/2,m);

তাহলে এবার ফাংশনে n এর মান যাবে 5 যা বিজোড় তাই

                 

              return(((x%m)*bigmod(x,n-1,m))%m);

তাহলে এবার ফাংশনে n এর মান যাবে 4 যা জোড় তাই

                  y=bigmod(x,n/2,m);

                  return ((y*y)%m);

এভাবে n এর মান 0 হলে বেস কেস রিটার্ন করবে 1 এর ফলে পপ হতে থাকবে অর্থাৎ 0 এর মান বের হওয়ার পর 1 এ যাবে এবং এর মান বের করবে, তারপর 2 এ যাবে, এভাবে ১০ এ গেলে আমরা আমাদের রেজাল্ট পেয়ে যাব ।

n= 0 then  bigmod(2,0,10)  --->  return 1 = 1

n= 1 then  bigmod(2,1,10)   ---> return(((x%m)*bigmod(x,n-1,m))%m); --->   (2* bigmod(2,0,10))%10 = 2

n= 2  then 

  bigmod(2,2,10)  

  y=bigmod(x,n/2,m);
  return ((y*y)%m);

 = (bigmod(2,1,10)* bigmod(2,1,10))%10= 4

n= 4 then   bigmod(2,4,10)  = (bigmod(2,2,10)* bigmod(2,2,10))%10=6

n= 5  then  bigmod(2,5,10)  =  (2 * bigmod(2,4,10))%10 =(2*6)%10=2

n= 10 then bigmod(2,10,10) = (bigmod(2,5,10)* bigmod(2,5,10))%10=4

সুতরাং আমরা আমাদের সর্বশেষ রেজাল্ট পেয়ে গেলাম । এভাবেই বিগ মড এর রিকার্সিভ ফাংশন কাজ করে ।

Related Problems : UVA 374 Big Mod
                         DevSkill 23 Another Bigmod Problem

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here