ইউক্লিডিয়ান অ্যালগরিদম হলো গ.সা.গু. বা গরিষ্ঠ সাধারণ গুণনীয়ক বের করার জন্য একটি দ্রুতগতির অ্যালগরিদম। এই অ্যালগরিদমের নামকরণ করা হয় ইউক্লিডের নামে যিনি তার Elements নামক বইয়ে বর্ননা করেছেন,
দুটি সংখ্যার গ.সা.গু. হল সেই বৃহত্তম সংখ্যা যা দুটি সংখ্যাকেই নিঃশেষে ভাগ করে। ইউক্লিডীয় অ্যালগরিদম যে নীতির উপর প্রতিষ্ঠিত তা হলো বৃহত্তর সংখ্যাটি থেকে ক্ষুদ্রতর সংখ্যাটি বিয়োগ করা হলেও তাদের গ.সা.গু. পরিবর্তিত হয় না। যেমন আমরা যদি দুইটি সংখ্যা ২৫০ এবং ১০৫ নেই যাদের গ.সা.গু. ৫ । ২৫০ থেকে ১০৫ বাদ দিলে পাই, ১৪৫। এখানে ১০৫ এবং ১৪৫ এর গসাগু ও ৫ হয়। এখন ১৪৫ থেকে ১০৫ বাদ দিলে পাবো ৪০। ১০৫ এবং ৪০ এর গ.সা.গু. ও ৫। এখন ১০৫ থেকে ৪০ বাদ দিলে পাবো ৬৫, ৬৫ থেকে ৪০ বাদ দিলে পাবো ২৫, ৪০ থেকে ২৫ বাদ দিলে ১৫, ২৫ থেকে ১৫ বাদ দিলে ১০, ১৫ থেকে ১০ বাদ দিলে ৫ এখন ১০ থেকে ৫ বাদ দিলে থাকে ৫। যা আমাদের গ.সা.গু.।
অর্থাৎ যতক্ষণ পর্যন্ত ছোট সংখ্যা আর বড় সংখ্যা সমান না হয় আমরা পর্যায়ক্রমিক বিয়োগ চালাতে থাকবো। অনেকটা নিচের মতো।
| 1 2 3 4 5 6 7 8 9 10 | int gcd(int a,int b){ while(a!=b){ if(a>b){ a-=b; //a বড় হলে a-b দিয়ে a কে আপডেট করবো। }else{ b-=a; //b বড় হলে b-a দিয়ে b কে আপডেট করবো। } } return a; } |
এখন উপরের কাজটিতে গসাগু বের করা গেলেও এতে সময় বেশি লাগবে। আমরা ইচ্ছে করলেই ভাগ করার মাধ্যমে এই প্রসেসকে O(log n) সময়ে নামিয়ে আনতে পারি। খেয়াল করি, ১০৫ এবং ২৫০ এর গসাগু বের করার সময় ১০৫ কে পর পর দুইবার ২৫০, ১৪৫ থেকে বিয়োগ দিতে হয়েছিলো। কেমন হয় যদি আমরা ভাগ এর মাধ্যমে করি? ১৪৫ থেকে ১০৫ বাদ দিলে পেয়েছিলাম ৪০। সুতরাং আমরা যদি ৪ এবং ৬ নং লাইনে বিয়োগ এর বদল ভাগশেষ (Modulo or %) বের করি তাহলেই ২ বারের কাজ ১ বারে হয়ে যাচ্ছে।
| 1 2 3 4 5 6 7 8 9 10 | int gcd_iterative(int a,int b){ while(a!=0&&b!=0){ if(a>b){ a%=b; }else{ b%=a; } } return max(a,b); } |
এখানে কয়েকধাপের বিয়োগের কাজ একবারেই সম্পন্ন হবে। যার জন্য আমরা O(log n) সময়ে ভাগশেষ বের করতে পারবো। যেহেতু ভাগশেষ বের করতেছি প্রতিবার, তার কোন না কোন সময় a অথবা b এর কোন একটি শুন্য হবে। তখন আমাদের লুপ থামবে এবং a, b এর মধ্যে যা অশূন্য তাকে রিটার্ন করবো।
উপরের কোডে আমরা একটি বিষয় খেয়াল করলাম। যেই সংখ্যাটি দিয়ে ভাগশেষ বের করা হচ্ছে তা সবসময় অন্যটির থেকে ছোট। এই আইডিয়া কাজে লাগিয়ে আমরা রিকার্শনের মাধ্যমে গ.সা.গু. বের করতে পারি।
রিকার্শনের মাধ্যমে গ.সা.গু. নির্নয়
| ধাপ | Update to | Update to | |||
| ১ | 250 | 105 | |||
| ২ | 105 | 40 | |||
| ৩ | 40 | 25 | |||
| ৪ | 25 | 15 | |||
| ৫ | 15 | 10 | |||
| ৬ | 10 | 5 | |||
| ৭ | 5 | 0 | যেহেতু তাই বলা যায় এর আগের বার b দ্বারা a কে ভাগ গিয়েছিলো। বর্তমানে a তখনকার b কে জমা রেখেছে। তাই a রিটার্ন করবো। |
উপরের ছকটি খেয়াল করি। আমরা ২৫০ এবং ১০৫ এর গসাগু বের করবো। এখানে । এখন, উপরের আলোচনা থেকে জানি, , এখানে । সুতরাং বের করতে হলে আমরা আগে বের করবো। এভাবে কোন এক সময় b দ্বারা a কে ভাগ করা যাবে। উপরের ৬ নং ধাপে যা হয়েছে। এসময় আপডেট হয়ে হবে এবং হবে (যেহেতু )। তাই ৭ নং ধাপে বেস কেসে কে GCD বা গ.সা.গু. হিসেবে রিটার্ন করেছি।
রিকার্শনের মাধ্যমে গ.সা.গু. নির্ণয়ের C++ কোড
| 1 2 3 4 | int gcd_recursion(int a,int b){ if(b==0) return a; // যখন b=0 হবে, তখন a আমদের গ.সা.গু.। return gcd_recursion(b,a%b); //a=b এবং b=a%b করে দিলাম রিকার্সিভ ফাংশন কলের মাধ্যমে। } |
৩ নং লাইনে আমরা উপরে যেভাবে বর্ণনা করেছি সেভাবেই রিকার্সিভ কল করেছি, এর মাধ্যমে প্যারামিটারে এবং পাঠিয়েছি। এভাবে যখনি ২ নং লাইনে b=0 পেয়েছি, a কে গ.সা.গু. হিসেবে রিটার্ন করেছি। কারণ 0 এবং a এর গ.সা.গু. a ই হবে।
এই কোডের টাইম কমপ্লেক্সিটি O(log n) যেখানে ।
গ.সা.গু. থেকে ল.সা.গু. (LCM) নির্ণয়
আমরা যদি O(log n) এ দুইটি সংখ্যার গ.সা.গু. বের করতে পারি, তবে খুব সহজেই ল.সা.গু. (Least Common Multiple) বের করা যায়। আমরা জানি,
, যেখানে হলো প্রদত্ত দুইটি সংখ্যা।
বা,
অর্থাৎ আমরা যদি দুইটি সংখ্যার গুণফলকে দুইটি সংখ্যার গ.সা.গু. দিয়ে ভাগ করি তবে আমরা এ ল.সা.গু. পাবো।
আজ এই পর্যন্তই। পরের লিখাটি Extended Euclidean algorithm নিয়ে । পরে দেখার নিমন্ত্রন রইলো। #happy_coding
Nice explanation. Thank you so much
💖
Thanks for your contribution to create my interest about it.
My pleasure ❤️