Modular exponentiation

Modular exponentiation: কন্টেস্ট প্রোগ্রামিংয়ে মডুলার এক্সপনেনটিয়েশন রিলেটেট প্রব্লেম মাঝে মাঝেই থাকে । বেশিরভাগ সময় নেইভ সল্যুশন  করতে গিয়ে দেখা যায় টাইম লিমিট খায় । এই ধরনের প্রব্লেমকে অপ্টিমাইজ করার জন্য কিছু টেকনিক বা অ্যালগরিদম আছে । আচ্ছা আজাইরা ইন্ট্রো গল্প বাদ দিয়ে চলেন শুরু করা যাক ।

বেসিক সমাধান -: এক্সপনেনটিয়েশনকে  নরমারলি x^n এইভাবে প্রকাশ করা হয় । তো এইটার রেজাল্ট বের করার জন্য বেসিক যেই সল্যুশন সেটা হলো x*x*x*x*......*x এইভাবে n টাইম পর্যন্ত গুন করা।  বেসিক এই সল্যুশন করতে মোটামুটি x*x^n-1 এইভাবে ভাঙতে হবে। এইটার একটা রিকারসিভ সল্যুশন যদি লেখি তাহলে কোড টা দারায় এইরকম

int power(int x,int n)

{

    if(n==0)

        return 1;

    return x*Power(x,n-1);

} 

এইটা মোটামুটি ইফিসিয়েন্টই মনে হচ্ছে তাই না ? এইটার টাইম কমপ্লেক্সিটি কত? আমিই বলে দেই O(n) । আচ্ছা প্রব্লেম ডেসক্রিপশনে যদি x^n এইখানে n এর মান যদি 10¹⁸ এইরকম থাকে তখন আমরা উপযুক্ত সমাধান পাবো ? তাহলে কি করতে হবে আমাদের আরও অপ্টিমাইজড সমাধান খোঁজা উচিৎ ।

অপ্টিমাইজড সমাধান-: x^n এর অপ্টিমাইজড সমাধান একটাই  আমাদের রান টাইম কমিয়ে নিয়ে আসতে হবে n টাইম পর্যন্ত গুন না করেই রেজাল্ট বের করতে হবে । আমরা যত তাড়াতাড়ি  x^n মান বের করতে পারবো আমাদের সল্যুশন তত ইফিসিয়েন্ট হবে।
আমাদের যেই n এর মান দেয়া থাকবে চেক করতে হবে সেইটা জোড় না বিজোড় ?
১ । n যদি জোড় হয় তাহলে x^n কে ভেঙ্গে (x^2)n/2 এই আকারে প্রকাশ করবো
  এইখানে কি হলো জাস্ট একটা স্টেপে আমরা n এর মানকে অর্ধেকে নিয়ে আসলাম । আমাদের রান টাইম আগের থেকে অনেক কম লাগতেছে কিন্তু।

২। n যদি বিজোড় হয় তাহলে n কে জোড় বানাতে হবে অর্থাৎ স্টেপটা হবে x*x^n-1 এইরকম
 উদাহরণ ঃ মনে করি আমাদেরকে 4¹⁰ এর মান বের করতে হবে। আমারা নরমালি ১০ বার ৪ কে গুন করলেই রেজাল্ট পেয়ে যাবো কিন্তু আমরা ১০ বার না আরও কম সময়েই রেজাল্টটা পেতে পারি । ওকে তাহলে স্টেপ গুলো শুরু করি

1.  এইখানে n এর মান ১০ যা একটি জোড়  সংখ্যা তাই আমরা প্রথম স্টেপেই একে ভেঙ্গে ফেলতে পারি    4¹⁰ ⥤ (4^{2)^5}⥤16⁵
2. এখন আমাদেরকে 16^5 মান বের করতে হবে । এইখানে n এর মান ৫ যা একটি বিজোড় সংখ্যা
   16⁵⥤16*16⁴⥤16*(16²)²
3. ফাইনালি আমরা 256^2 কে একটা স্টেপে গণনা করলেই রেজাল্ট পাচ্ছি । 16*256*256=1048576 

Code:

int ext(int x,int n)

{

    if(n==0)

        return 1;

    else if(n%2 == 0)        //n is even

        return exp(x*x,n/2);

    else                             //n is odd

        return x*exp(x*x,(n-1)/2);

}

তাহলে আমরা বলতে পারি এইটা একটা ইফিসিয়েন্ট ম্যাথড । আমরা ১০ স্টেপের কাজকে জাস্ট ৩ স্টেপেই করে ফেললাম ।
এইটার কমপ্লেক্সিটি হবে  O(log N)

আচ্ছা এখন এইরকম রেজাল্ট যদি আসে যেইটা ডেটা টাইপের রেঞ্জের বাইরে তখন কি করবো ? 😕😕সেইখেত্রে আমাদেরকে মডুলাস (%) ব্যাবহার করতে হবে  এবং আমাদেরকে x^n এর মান বের করার পরিবর্তে (x^n)%m বের করতে হবে ।
উদাহরণ ঃ আমরা যদি 2¹⁰⁹ এর মান বের করতে চাই তাহলে O(n) সল্যুশনে এইটা টাইমআউট হবে , O(log N) সল্যুশনে এইটা যথা সময়ে রান হবে কিন্তু গারবেজ মান দিবে । তো এই প্রবলেম থেকে বাচার জন্য অবশ্যই মডুউল অপারেশান ব্যাবহার করতে হবে ।

Code:

  

int exp(int x,int n,int M)

{

    if(n==0)

        return 1;

    else if(n%2 == 0)        //n is even

        return exp((x*x)%M,n/2,M);

    else                             //n is odd

        return (x*exp((x*x)%M,(n-1)/2,M))%M;

}

আজকে এই পর্যন্তই  হ্যাপি কোডিং 😊😊