2⁸ বা b^p আসলে কী? 2 কে 8 বার গুণ বা b কে p বার গুণ করলে যা আসবে তাই হচ্ছে 2⁸ বা b^p। 2⁸ = 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 = 264।
এটি সি/সি++ তে খুব সহজেই বের করা যায় বিল্ড ইন ফাংশন pow(b, p); ব্যাবহার করে(b মানে Base এবং p মানে Power)। বিল্ড ইন ফাংশনের সাহায্য না নিয়েও খুব সহজেই এটি বের করে ফেলতে পারি। শুধু p বার লুপ চালিয়ে b কে p তম বার গুণ করব। খুব সহজ কাজ, আশা করছি কোড দেখার আগেই পারবেন।
|
// function to find power
int power(int b, int p) {
// n is for calculate b^p and b for Base and p for Power
int n = 1;
for (int i = 0;i < p;i++) {
// multiply b with n in p times
n *= b;
}
return n;
}
|
এই ফংশনের কমপ্লেক্সিটি হচ্ছে, O(p)। যদি বলা হয়, p = 1e9 (1e9 = 1000000000)। তাহলে কিন্তু সময় অনেক লেগে যাবে অথবা, যদিও p এর ভ্যালু কিছুটা কম থাকে তাহলেও কিন্তু শুধু পাওয়ার বের করতেই বেশ খানিকটা সময় অপচয় হয়ে যাবে। তাহলে এখন উপায় কী?
2^8 কে বের করতে হলে 8 টি 2 কে গুণ করতে হবে এবং উত্তর হবে 264। যদি, 4 টি 2 কে গুণ করি তাহলে বের হবে 16 এবং 16X16 = 264। এখন কিন্তু আমাদের অর্ধেক কাজ কমে গেছে। আবার, 2 টি 2 কে গুণ করলে হয় 4 এবং 4 কে 4 দিয়ে গুণ করলে হয় 16। আবারো অর্ধেক কাজ কমে গেছে।
input: b = 2, p = 8, n = 1
b ← b X b = 2 X 2 = 4 p/2 = 8/2 = 4 n = 1, b = 4
b ← b X b = 4 X 4 = 16 p/2 = 4/2 = 2 n = 1, b = 16
b ← b X b = 16 X 16 = 264 p/2 = 2/2 = 1 n = 1, b = 264
n ← b X n = 264 X 1 = 264 p/2 = 1/2 = 0 n = 264, b = 264
তাহলে 8 টি কাজ কে মাত্র 4 ধাপেই শেষ করে ফেললাম। আচ্ছা, ছোট সংখ্যার জন্য হয়ত এটি খুব বেশি কম মনে নাও হতে পারে। তবে এটি যে আসলেই কত কম তা বুঝার জন্য একটি উদাহরণ দেই। INT_MAX অর্থাৎ p = 2147483647 হলে 31 ধাপেই বের করা সম্ভব!!!
এখন প্রশ্ন থাকতে পারে, p বিজোর হলে? p বিজোর হলে n এর সাথে base অর্থাৎ b কে গুণ করে n এর মাঝে রেখে দিব, যেমন টা উপরে শেষ ধাপে করেছি। আচ্ছা p = 10 এর জন্য দেখে নিতে পারি।
input: b = 2, p = 10, n = 1
b ← b X b = 2 X 2 = 4 p/2 = 10/2 = 5 n = 1, b = 4
n ← b X n = 4 X 1 = 4 p-1 = 5-1 = 4 n = 4, b = 4
b ← b X b = 4 X 4 = 16 p/2 = 4/2 = 2 n = 4, b = 16
b ← b X b = 16 X 16 = 264 p/2 = 2/2 = 1 n = 4, b = 264
n ← b X n = 264 X 4 = 1024 p/2 = 1/2 = 0 n = 1024, b = 1024
|
int power(int b, int p) {
int n = 1;
while (p > 0) {
// if p is odd then we multiply base with n
if (p%2 != 0) n = n*b;
// now we will multiply base with base
b *= b;
p /= 2;
}
return n;
}
|
এই ফংশনের কমপ্লেক্সিটি হচ্ছে, log2(p)। এখন, 2^8 হবে 3 ধাপে এবং 2^10 হবে 4 ধাপে। উপরে দেখলাম, হইছে 4 ও 5 ধাপে কিন্তু আপনি বলছেন 3 ও 4 ধাপে, কেন? কোড একটু ভালো করে খেয়াল করলেই আশাকরি বুঝতে পারবেন। যদি বিজোর হয় তাহলে কিন্তু 1 বিয়োগ করেই আবার লুপে ফেরত যাচ্ছি না। বেইজ কে বেইজ দিয়ে গুণ করে এরপর বিজোর কে দুই ভাগ করে দিচ্ছি। বিয়োগ না করার ফলেও কোন সমস্যা হবে না। কারণ এখানে ইন্টিজার ডিভিশন হচ্ছে।
আচ্ছা, এই ফাংশন কি 10^100 বের করতে পারবে? এমন প্রশ্ন নিশ্চয়ই আপনার মনেও ঘুরছে? উত্তর হচ্ছে, সেটি সম্ভব নয়। কারণ, 10^100 মানে 1 এর পরে 100 টি শূণ্য থাকা সংখ্যা long long ডাটা টাইপেও আটবে না।
তাহলে, 10007 কে দিয়ে মড করে করে রেজাল্ট বের করব। তাহলে, উত্তর int ডাটা টাইপেই আটবে। গুণ করার সময় মড করে রেখে দেওয়া নিয়ে যদি আইডিয়া না তাহলে এই
ভিডিও টি দেখে নিতে পারেন। নিচের ফাংশনে
বিটওয়াইজ অপারেটর ব্যাবহার করেছি, এতে প্রোগ্রাম আরো ফাস্ট হবে।
|
int mod = 10007;
int power(int b, int p) {
int n = 1;
while (p > 0) {
if ((p&1) != 0) { // this means p%2 != 0;
n = ((n%mod) * (b%mod)) % mod;
}
b = ((b%mod) * (b%mod)) % mod;
p = p >> 1; // this means p /= 2;
}
return n;
}
|
এবার এই কাজটিই রিকারশন দিয়ে করব। রিকারশন দিয়ে কোড অনেক সহজেই করা যায় এবং কোড তুলনামূলক ছোট হয়। তবে টাইম ও মেমোরি নিয়ে সতর্ক থাকতে হয়।
(2 X 2 X 2 X 2 X 2 X 2 X 2 X 2)
(2 X 2 X 2 X 2) X (2 X 2 X 2 X 2) গুণফলের সাথে নিজেকেই গুণ
(2 X 2) X (2 X 2) X (2 X 2) X (2 X 2)
(2) X (2) X (2) X (2) X (2) X (2) X (2) X (2)
যদি রিকারশন সম্পর্কে জানেন তাহলে সম্ভবত শুরুতেই আইডিয়া পেয়ে গিয়েছিলেন রিকারসিভ এর সম্পর্ক আছে। যাইহোক, চট করে কোড টি দেখে নেই।
|
// also pass mod value in function
int power(int b, int p, int mod) {
if (p==0)return 1%mod;
if (p%2) { // if p is odd
return ((power(b, p-1, mod) % mod) * (b % mod)) % mod;
}
int x = power(b, p/2, mod);
return ((x%mod) * (x%mod)) % mod;
}
|
বেইজ কেস শুণ্যা কারণ, আমরা জানি b^0 = 1।
প্র্যাক্টিস প্রবলেমঃ
এই বিষয়ে আরো টিউটোরিয়াল।
No comments