Modulus হিসাব করার ছোট্ট একটু চিন্তা ভাবনা।

 আসো  Modulus (%) বের করি। 

ধরো তোমাকে ২ টা সংখ্যা a আর b দেওয়া আছে। তোমাকে (a+b)%c বের করতে হবে। যেখানে a,b,c এর মান 2^⁶⁴ - 1 অব্দি হতে পারে  যা c/c++ সর্বচ্চ মান (মানে unsigned long long int এ। এর চেয়ে বেশি ভ্যালু হলে আমরা সেটা String দিয়ে হ্যান্ডেল করি)।  

কি ভাবছ? অনেক সহজেই  ans=(a+b)%c;  বের করলেই হয়ে গেলো তাইনা ?

আচ্ছা ধরি, a=18446744073709551614, b=100, ans = (18446744073709551614 +  100 ) % 18446744073709551615   [যেখানে c=2^⁶⁴ - 1] এভাবে  বের করা কি সম্ভব?,

আসলে কি হবে এখানে ?  (18446744073709551614 + 100) যোগ করলে overflow হবে। (2^⁶⁴ - 1 এর চেয়ে বেশি হয়ে যাবে যা unsigned long long int  এও আটানো সম্ভব হবে না), যদি যোগ-ই করতে না পারি তাহলে কেমনে mod c (%c) বের করবো? যাক তাহলে  ans = (a+b)%c;  সমাধান কাজ করলো না।

আচ্ছা আরেকটু ভাবি,  উপরের মতো করে যদি না হয় তাহলে আমাদের পরবর্তি ধাপ কি হতে পারে? উমম,!  আমরা জানিতো  (a+b)%c থাকলে আমরা এটাকে (a%c + b%c) %c আকারে লিখতে পারি। তারমানে  ans = (a%c + b%c) %c; হুম, এখন এভাবে সমাধান করার চেস্টা করি। :-)

ans = (18446744073709551614%18446744073709551615 + 100% 18446744073709551615 ) % 18446744073709551615;

আচ্ছা এটা করলে কি হবে ?

18446744073709551614 % 18446744073709551615 এটা করলে কি কোন লাভ হবে? 

আসলে এটার mod (%) বের করলে 18446744073709551614 এটাই হই আর 100 % 18446744073709551615 এটা করলে 100-ই হবে । তাহলে আমাদের সমাধানটা দাড়ালো কি?

 ans = (18446744073709551614 + 100) % 18446744073709551615

এমনটাই থেকে গেলো নাকি,আমরা উপরে দেখলাম এভাবে সমাধান করলেও overflow হচ্ছে। ২য় উপয়েও কাজ হলোনা। তাহলে এখন কি উপাই? 

 

আচ্ছা এইবার আমরা একটু অন্য উপায়ে দেখি। 

 

     x = a%c 

     y = b%c 

a আর b যদি c এর সমান অথবা বড় হয়, তাহলে আমরা শুধু x,y এর মধ্যে তা কমিয়ে ছোট করে নেওয়ার চেষ্টা করেছি। 

 

     z = c-x;

z এর মধ্যে x কতটুকু ছোট c এর চেয়ে তা রেখেছি। 

 

      if(z<=y)         

        ans = (y-z)%c;

      else             

        ans = x+y;     

z যদি y এর চেয়ে ছোট/সমান হয় তাহলে আমরা ans = (y-z)%c লিখতে পারি, অন্যথায় ans = x+y লিখতে পারি। 

 

এখন দেখি আমাদের সমাধানের সাথে উপরের উদাহরণ কাজ করে কি না। 

 x = 18446744073709551614%18446744073709551615 =18446744073709551614 

  y = 100%18446744073709551615 = 100

এখন  z = 18446744073709551615 - 18446744073709551614 =1

এখন দেখা যাচ্ছে যে , z<=y, তাহলে আমরা লিখতে পারি ঃ  

ans =  (100-1) % 18446744073709551615 = 99

 এখানে কোন হিসাব-ই কিন্তু আমাদের এইবার overflow হয় নাই। 

 

হাতে কলমে আর কয়েকটা উদাহরণ চেষ্টা করলেই জিনিসটা  বুঝে ফেলবা। 

[বিঃদ্র: আমাদের কম্পিউটারের কম্পাইলার গুলাতে ১ম,২য় সমাধান কাজ করে যেতে পারে, কিন্তু অনলাইন জাজ-এ কাজ করবে না। ]

 

কারো কোন জিজ্ঞেসা/সংশোধনী  থাকলে কমেন্ট করে বলতে পার।