Tag: ইউক্লিড

ইউক্লিডিয়ান অ্যালগরিদম পৃথিবীর প্রাচীন অ্যালগরিদমগুলোর মধ্যে অন্যতম। প্রাচীন গ্রিক গণিতবিদ ইউক্লিডের নামানুসারে প্রচলিত এই অ্যালগরিদমটি দুইটি সংখ্যার গ.সা.গু নির্ণয়ের সবচেয়ে কার্যকর (efficient) পদ্ধতি। গ.সা.গু এবং ল.সা.গু বের করার সময় অনেক বিগিনার লেভেলের প্রোগ্রামারদের বেশ সমস্যা হয়ে থাকে। আজকের এই লেখার আমরা জানবো কিভাবে ইউক্লিডিয়ান অ্যালগরিদমের সাহায্যে সহজেই দুইটি সংখ্যার গ.সা.গু বের করা যায়। মজার ব্যাপার হচ্ছে, এই গ.সা.গু থেকেই ছোট্ট একটি সূত্র দিয়ে আমরা ল.সা.গু বের করার কাজটিও করতে পারি।

ইউক্লিডের অ্যালগোরিদম বা গ.সা.গু নির্ণয়ের অ্যালগোরিদমটি নিম্নরূপঃ

অ্যালগরিদম দেখে ঘাবড়ানোর কিছু নেই। আমরা অ্যালগরিদমটি বুঝতে চেষ্টা করি।

প্রথমেই দেয়া আছে একটি ফাংশন যার নাম gcd() এবং এই ফাংশনটির দুইটি প্যারামিটার a,b। এখানে, a এবং b হচ্ছে সেই দুইটি সংখ্যা আমরা যেগুলোর গসাগু বের করতে চাচ্ছি। ফাংশনটিতে প্রথমেই রয়েছে একটি while লুপ যেটি b-এর মান শূন্য না হওয়া পর্যন্ত চলবে। এখানে, একটি টেম্পোরারি ভ্যারিয়েবল t ব্যবহার করা হয়েছে। প্রথমে b-কে টেম্পোরারিতে রাখা হয়েছে। এরপর b-এর মান আপডেট হয়েছে a mod b দিয়ে। এখানে, mod হচ্ছে মডুল্যাস। অর্থাৎ, a-কে b দিয়ে ভাগ করে যেটি ভাগশেষ থাকবে সেটি হবে b-এর পরিবর্তিত মান। পরের লাইনে আছে a := t; এখানে a-এর নতুন মান হবে t-এর মান। লুপের প্রথম লাইনে আমরা t-এর মান পাচ্ছি b। তাহলে, a-এর মান হবে b-এর পুরনো মানটি (আপডেটেট মানটি নয়)। এভাবে লুপের ভিতরের কাজগুলো হতে থাকবে যতক্ষণ না b-এর মান শূন্য না হয়। লুপের কাজ শেষ হওয়ার পর ফাংশনটি a-এর মান রিটার্ন করবে, যেটি আমাদের কাঙ্ক্ষিত gcd()-এর মান বা গ.সা.গু।

একটি উদাহরণ দিলে ফাংশনটির কার্যক্রম আমাদের কাছে পরিষ্কার হবে। ধরা যাক, a= 12 এবং b = 16 , এদের গ.সা.গু বের করতে হবে। অ্যালগরিদম অনুযায়িঃ

1. a=12 , b = 16
2. while(b!=0) এভাবে b এর মান যতক্ষণ 0 না হবে লুপটি ততক্ষণ চলবে। অর্থাৎ লুপের ভিতরের তিনটি স্টেপ আমরা b এর মান 0 না হওয়া পর্যন্ত করবো।
3. t = 16; b = 12%16  এখানে যেহেতু 12 কে 16 দ্বারা ভাগ করা যায় না, তাই ভাগশেষ হবে 12, সুতরাং b = 12 , a = t = 16 (যেহেতু, প্রথমেই আমরা t এর মান 16 দিয়েছি যেটি b-এর প্রাথমিক মান।)
4. তিন নাম্বার স্টেপে আমরা a এবং b এর আপডেটেট ভ্যালু পেয়েছি। a = 16 এবং b= 12 . এখন আমাদের t = b = 12; b = a%b = 16%12 = 4; a =t = 12।
5. এখন a = 12, b = 4 এখন t = b = 4;  b = a%b = 12%4 = 0; a = 4; এখানে আমরা b এর মান জিরো পেয়ে গেলাম তাই এই লুপটি আর execute করবে না। এটি a-এর ভ্যালু return করবে 4।

আমরা যদি এখন এটি সি প্রোগ্রামিং এর সাহায্যে কোড করি, আমাদের কোডটি হবে এমনঃ

এই ফাংশনটির সাহায্যে খুব সহজেই গ.সা.গু নির্ণয়ের কাজটি করা যাবে। এবার দেখা যাক ইউক্লিড সাহেবের এই অ্যালগরিদমটি দিয়ে আমরা ল.সা.গু নির্ণয় করতে পারি কি না। ল.সা.গু নির্ণয় করার একটি সহজ সূত্র আছে। সূত্রটি এমনঃ

দুটি সংখ্যার ল.সা.গু = দুটি সংখ্যার গুণফল / দুটি সংখ্যার গ.সা.গু

দুটি সংখ্যার গ.সা.গু বের করার নিয়ম এবং দুটি সংখ্যার গুণফল নির্ণয় করার প্রক্রিয়া আমরা জানি। সেখান থেকে খুব সহজেই আমরা ল.সা.গু বের করতে পারবো।

লেখক : তামান্না নিশাত রিনি।