এ্যালগরিদমঃ বিগ মড (Big Mod)

যেটার জ্ঞান আবশ্যকঃ রিকার্শন।

ছোট মরিচের ঝাল দেখা যাক আজকে-

আপনাকে যদি জিজ্ঞেস করি 17⁵⁴ % 81 = কি? কি বলবেন? থামেন, ক্যালকুলেটর কই!! ওকে, ক্যালকুলেটরে চেষ্টা করে দেখুন। কি!  ক্যালকুলেটর ফেইল মারছে?? ভেরী গুড।

এই কাজটা Big Mod এর মাধ্যমে খুব সহজে করতে পারি। যেখানে আমরা ছোট্ট একটি Mathematical নোটেশন ব্যাবহার করব। দেখি তাহলে –

(A * B ) % C = ( A % C * B % C ) % C

যেমনঃ-

35 % 3 = (5 * 7) % 3

            = (5 % 3 * 7 % 3 ) % 3

            = (2 * 1) % 3

            = 2

তাহলে দেখিঃ –

17⁵⁵ % 81 = (17 * 17⁵⁴) % 81

                            = (17 % 81 * 17⁵⁴ % 81) % 81

এখন 17⁵⁴ % 81 = কি?

17⁵⁴ % 81 = (17²⁷ * 17²⁷) % 81

                           = (17²⁷ % 81 * 17²⁷ % 81) % 81

আবার 17²⁷ % 81 = কি?

17²⁷ % 81 = (17 * 17²⁶) % 81

                           = (17 % 81 * 17²⁶ % 81) % 81

একইভাবে আমরা পাইঃ-

17²⁶ % 81 = (17¹³ % 81 * 17¹³ % 81) % 81

17¹³ % 81 = (17% 81 * 17¹² % 81) % 81

17¹² % 81 = (17⁶ % 81 * 17⁶ % 81) % 81

17⁶ % 81 = (17³ % 81 * 17³ % 81) % 81

17³ % 81 = (17 % 81 * 17² % 81) % 81

17² % 81 = (17 % 81 * 17 % 81) % 81

17 % 81 = 17

এখন নিচ থেকে ভ্যালূগুলো উপরের Equation গুলোতে বসিয়ে একটু ক্যালকুলেট করলে উত্তর পাওয়া যাবে।

নিচের ছবিটি দেখি এখন –

 * যদি উপরের Equation গুলোর একটিও বুঝতে না পারেন তাহলে আবার দেখুন নিচে যাওয়ার দরকার নেই।

দেখুন আমরা পাওয়ারকে সর্বনিন্ম 1 এ নিয়ে এসেছি (চিত্রে শেষ লাইন দেখুন) এভাবে শেষ লাইন থেকে হিসেব করা মান তার আগের লাইনে বসিয়েছি এবং শেষ পর্যন্ত প্রথম লাইনে ফিরে গিয়েছি।

২ টা ব্যাপার লক্ষ্য করুন, পাওয়ার যখন জোড় ছিল তখন কি করেছি এবং যখন বিজোড় ছিল তখন কি করেছি।

মনেকরি,

base হচ্ছে  = b

power হচ্ছে = p

Divisor হচ্ছে = d;

যখন পাওয়ার বিজোড়, আমরা করেছি,

(b % d * b ^(p-1) % d ) % d

যখন পাওয়ার জোড়, আমরা করেছি,

(b ^(p/2) % d * b ^(p/2) % d ) % d

বা, square( b ^(p/2) % d ) % d

এই কাজটা আমরা পাওয়ার জিরো হওয়ার আগ পর্যন্ত করেছি। মানে p থেকে 1 পর্যন্ত। তাহলে আমাদের কাজ শেষ হয়ে গিয়েছে কখন? যখন p এর মান জিরো হয়ে গিয়েছে। মানে রিকার্শন ব্রেক হওয়ার কন্ডিশন হচ্ছে এটি, যখন p = 0 ।

আর একটা ব্যাপার দেখুন আমরা লাস্ট স্টেপ থেকে মান তার আগের স্টেপে পাঠিয়ে দিয়েছি।

এখন তাহলে কোড করি –

মনেকরি আমাদের ফাংশনের নামে bigMod যার ৩ টি parameter (b,p,d) আছে –

int bigMod(int b, int p, int d)
{
   if(p == 0 )
      return 1;   
   if( p % 2 != 0 )
   {
      return ( b % d * bigMod( b, p-1, d ) ) % d ;
   }
   else
   {
      return ( square( bigMod( b, p/2, d ) ) ) % d;   
   }
}
int square(int n)
{
   return n*n;
}

তাহলে আমরা এ্যালগরিদম ও কোড দুটোই বুঝতে পেরেছি। ঝটপট তাহলে ১ টি ACM সলভ করে ফেলি।
ACM প্রবলেমঃ 374 - Big Mod
পিডিএফ হিসেবে ডাউনলোড করুনঃ ডাউনলোড