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

চিত্র হতে দেখা যাচ্ছে যে পাওয়ার এর সর্বশেষ মান 1 এবং পাওয়ার 0 হলে \(2^{0}=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^{10} = 2^5 \times 2^5\)

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

\(y \times y\) কারন \(2^{5} \times 2^{5}\) এর মান হল \(2^{10}\) , \(2^{2} \times 2^{2}\) এর মান হল \(2^{4}\)

পাওয়ার এর মান বিজোড় হলেও দুই ভাগে ভাগ করতে হবে । এক্ষেত্রে বিজোড় পাওয়ার থেকে ১ বিয়োগ করে যা আসবে তার সাথে বেস ( এখানে ২) কে গুন করতে হবে । যেমন \(2{^5} = 2{^4} \times 2{^1}\)

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 bigmod(2,0,10)  --->  return 1 ---> মান 1
n= 1 bigmod(2,1,10)   ---> return(((x%m)*bigmod(x,n-1,m))%m);  ----> (2* bigmod(2,0,10))%10 = 2

n= 2 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   bigmod(2,4,10)  = (bigmod(2,2,10)* bigmod(2,2,10))%10=6
n= 5   bigmod(2,5,10)  =  (2 * bigmod(2,4,10))%10 =(2*6)%10=2
n= 10  bigmod(2,10,10) = (bigmod(2,5,10)* bigmod(2,5,10))%10=4

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

Related Problems : 

UVA 374 Big Mod