আমরা এর আগের ইউক্লিডিয়ান অ্যালগোরিদম নিয়ে লিখায় দেখেছিলাম কিভাবে দুইটি সংখা এর গসাগু এ বের করা যায়। ইউক্লিডিয়ান অ্যালগোরিদমের বর্ধিত ভার্সনের (এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম বা Extended Euclidean algorithm ) মাধ্যমে আমরা গ.সা.গু বের করার পাশাপাশি একটি সমীকরণ সমাধান করা যায় ।
এখানে হলো প্রদত্ত দুটি পূর্ণসংখ্যা যাদের গসাগু বের করতে হবে এবং হলো এর সহগ এবং এরাও দুইটি পূর্ণ সংখ্যা। আমরা এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগোরিদমের এর মাধ্যমে এর মান বের করতে পারবো। ‘
Extended Euclidean (এক্সটেন্ডেড ইউক্লিডিয়ান) algorithm Bangla tutorial
এখানে আমাদের জেনে রাখা জরুরি যে সবসময় এর এমন পাওয়া সম্ভব যার জন্য সত্য হবে। এবং ই হলো সবথেকে ছোট ধনাত্মক সংখ্যা যাকে এর এমন linear combination রূপে লিখা সম্ভব। প্রমান এখানে (Bézout’s Lemma)।
আমরা গত লিখায় যেই কোডটা করেছিলাম সেই কোডটাকে আবার একটু দেখি,
| 1 2 3 4 | int gcd(int a,int b){ if(b==0) return a; // যখন b=0 হবে, তখন a আমদের গ.সা.গু.। return gcd(b,a%b); //a=b এবং b=a%b করে দিলাম রিকার্সিভ ফাংশন কলের মাধ্যমে। } |
এখানে প্রতিবার আমরা এবং এর মাধ্যমে রিকার্সিভ কল করেছি। সুতরাং আমরা লিখতে পারি,
বা এখানে [ভাগশেষ (b)= ভাজ্য (a) – ভাগফল x ভাজক (b)] এবং , এর সমতুল্য।
ধরা যাক ইনপুট এর জন্য আমাদের সমাধান হলো । তবে (1) নং সমীকরণ থেকে আমরা লিখতে পারি,
… যেহেতু এবং
এখানে অনেকের কনফিউশন তৈরি হয়, এখানে এ b লিখেছি কারণ প্রতিবার রিকারসিভ কল করার সময় a এর মান হিসেবে b কে পাস করা হয় [a=b]। একই ভাবে লিখার কারণ হলো রিকার্সিভ কল করার সময় b এর মান হিসেবে ইনপুট দেয়া হয় [b=a%b]।
এখন সবকিছু মাথা থেকে ঝেরে ফেলি। ধরা যাক আমরা রিকার্সিভ কল করতে করতে বেস কেসে (Base case) এসে পৌছালাম। আমরা জানি বেস কেসে এবং এর মান গ.সা.গু.র সমান হয়। তাই । আমরা যদি এসময় এর সমাধান করার চেষ্টা করি তবে কিন্তু সহজেই বলতে পারি, হবে। কারণ,
বিশেষ দ্রষ্টব্য: এর মান আমরা যাই নিই, আমাদের সমীকরণ সত্য হবে।
সুতরাং আমরা বলতে পারি বেস কেসে আমরা এর সমাধান পেয়েছি, যেখানে এবং । এই সমাধান কাজে লাগিয়ে আমরা প্রদত্ত এর জন্য এর মান বের করবো।
এখন যদি আমাদের একটি সমাধান হয় তবে
(1) এবং (2) নং সমিকরনের এর সহগ সমীকৃত করে পাই,
হয়ে গিয়েছে। আমরা সমস্যার সমাধান পেয়ে গিয়েছি। এখানে আমরা আগের স্টেট এর সমাধান কাজে লাগিয়ে বর্তমান স্টেটের এর মানের জন্য সমাধান বের করতেছি। এভাবে রিকার্সিভ কল করে আমরা প্রদত্ত এর জন্য সমাধান বের করবো।
আশা করি এই পর্যন্ত বুঝা গিয়েছে, কোড দেখলে পরিস্কার হয়ে যাবে ইনশাআল্লাহ।
Extended Euclidean (এক্সটেন্ডেড ইউক্লিডিয়ান) algorithm Bangla – Code implementation with C++
নিচে আমরা C++ ব্যবহার করে এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদমের ইমপ্লিমেন্টেশন করেছি। এখানে extended_euclid() ফাংশনটা 4 টি প্যারামিটার নিবে। এর মধ্যে প্রথম দুইটি দুইটি পুর্ন সংখ্যা ইনপুট নিবে যাদের গসাগু আমরা বের করবো। পরের দুইটি প্যারামিটার প্রথমত কোন মান নিবে না, কিন্তু রিকার্সিভ ভাবে সমিকরনের সমাধান বহন করে আনবে। আর এই ফাংশন একটি পূর্ণসংখ্যা বা Integer রিটার্ন করবে যা এর গ.সা.গু.।
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <bits/stdc++.h> using namespace std; int extended_euclid(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return a; } int x1,y1; int gcd=extended_euclid(b,a%b,x1,y1); x=y1; y=x1-floor(a/b)*y1; //cout<<x<<" "<<y<<endl; return gcd; } int main(){ int x,y; int gcd=extended_euclid(12,8,x,y); cout<<gcd<<" "<<x<<" "<<y<<endl; return 0; } |
এই অ্যালগরিদমের দুইটি অংশ আছে। প্রথম অংশ ফাংশনের শুরু থেকে লাইন ১১ পর্যন্ত এবং দ্বিতীয় অংশ ১২ থেকে ফাংশনের শেষ পর্যন্ত। প্রথম অংশে আমরা রিকার্সিভ কল করার মাধ্যমে বেস কেস পর্যন্ত আসি যেখানে ফাংশন কলের ধাপ শেষ হয় এবং রিটার্ন করে উপরে যাবার ধাপ শুরু হয়।
উপরের চিত্রটি দেখি। আমরা int gcd=extended_euclid(b,a%b,x1,y1); এই লাইনের মাধ্যমে রিকার্সিভ কল করতে থেকেছি, যতক্ষন পর্যন্ত বেস কেস b=0 তে না পৌছাই। প্রথম ধাপে a=12, b=8 এখানে a এবং b এর গসাগু বের করবো। এর পরের ধাপে a=8, b=4 এবং তার পরের ধাপে a=4, b=0।
যখনি b=0, তখন আমরা বেস কেসে চলে এসেছি। আমরা শুরুতে দেখেছিলাম, যদি হয় তবে এ x এবং y এর মান যথাক্রমে 1,0 কারণ এখানে ।
পরের অংশে আমরা x এবং y এর মান হিসাব করার মাধ্যমে উপরে যেতে থাকি gcd এর মান তার কলার ফাংশন কে রিটার্ন করার মাধ্যমে।
উপরের ডায়াগ্রাম খেয়াল করুন। আমি রিকার্সিভ কলের কোন পর্যায়ে চলকের মান কত তাকে প্রকাশ করেছি। আশাকরি বুঝতে সুবিধা হবে।
যখন আমরা extended_euclid() ফাংশন কল করেছি তখন কে আমরা Call by reference এ প্রেরণ করেছি। এতে করে x1 এবং y1 এর মাধ্যমে আমরা প্রতিটি রিকার্সিভ কলের সমাধান পাবো। যা ব্যবহার করে আমরা এর মান বের করতে পারবো।
কোডে x=y1 এবং y=x1-floor(a/b)*y1 এর মাধ্যমে আমরা x এবং y এর মান বের করে গিয়েছি। এখানে x এবং y কে আপডেট করার সময় এর পূর্ববর্তী রিকার্সিভ স্টেজের x1 এবং y1 এর মান পরিবর্তন হবে, যেহেতু x এবং y কে রেফারেন্সের মাধ্যমে ইনপুট দেয়া হয়েছে। এভাবে একসময় আমরা এর সমাধান পাবো।
Practice Problems
আজকে এই পর্যন্তই। পরবর্তী লিখাতে সংখ্যাতত্ত্বের অন্য কোন বিষয়ে আলোচনা করবো। সেই পর্যন্ত #Happy_coding.
