ইউক্লিডিয়ান অ্যালগরিদম

$GCD(a,b) = GCD(b,a-b)$

$GCD(a,b) = GCD(b,a (mod b))$

$GCD(a,0) = a$

$GCD(0,0) = undefined$

ক্লাস থ্রি-ফোরে থাকতে আমরা সবাই লসাগু-গসাগু বের করতে শিখেছিলাম। গসাগু বের করার অনেকগুলো পদ্ধতির মধ্যে অন্যতম একটা পদ্ধতি হলো “ইউক্লিডিয়ান অ্যালগরিদম”। তবে অবাক করার বিষয় হলো, এই অ্যালগরিদম কেবল গসাগু বের করতেই কাজে লাগে না, এর রয়েছে নানাবিধ ব্যবহার।

ইউক্লিডিয়ান অ্যালগরিদমের মূল ব্যবহার হলো দুটি (বা অনেকগুলো) সংখ্যার গসাগু নির্ণয়ে। গসাগু কী জিনিস? সবচেয়ে বড় যে সংখ্যা দুটি সংখ্যারই উৎপাদক, সেটিই হলো তাদের গসাগু। যেমন, $36$ আর $66$ , এই দুটি সংখ্যারই উৎপাদক হলো $2, 3, 6$ । যেহেতু $6$ সবচেয়ে বড়, তাই $6$ হল গসাগু (গরিষ্ঠ বা সবচেয়ে বড় সাধারণ গুণনীয়ক)। ইংরজিতে একে বলা হয় $Greatest Common Divisor (GCD)$ । দুটি সংখ্যা $a, b$ এর গসাগুকে প্রকাশ করা হয় এভাবে – $GCD(a,b)$ ।

এখন ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে কী করে এই গসাগু বের করা যায়? ছোটবেলায় ভাগ করে ভাগশেষ যেভাবে গসাগু বের করা হতো, সেই পদ্ধতিই আসলে ইউক্লিডিয়ান অ্যালগরিদম। একটু ভেঙে লিখলে এরকম দাঁড়ায়ঃ

৩৬ ) ৬৬ ( ১ $\implies$ ছোট সংখ্যা দিলে বড় সংখ্যা ভাগ

৩৬

ভাগশেষঃ ৩০ ) ৩৬ ( ১ $\implies$ ভাগশেষ দিয়ে আগের ছোট সংখ্যা ভাগ

৩০

ভাগশেষঃ ৬ ) ৩০ ( ৫ $\implies$ নতুন ভাগশেষ দিয়ে আগের ভাগশেষ ভাগ

৩০

ভাগশেষঃ ০ $\implies$ ভাগশেষ $0$ না আসা পর্যন্ত চলবে!

যখন ভাগশেষ $0$ হয়ে গেল, আমাদের কাজ শেষ হয়ে গেল! শেষে যে সংখ্যাটি দিয়ে ভাগ করা হল, সেটিই গসাগু ( $6$ )।

তাহলে এটি কিভাবে কাজ করে? ইউক্লিডিয়ান অ্যালগরিদম মূলত দুটি ভিত্তিতে কাজ করে। মনে করি, দুটি সংখ্যা $A, B (A \leq B)$ এর গসাগু বের করতে হবে।

ভিত্তি ০১। যদি ছোট সংখ্যাটি ( $B$ ) হয় $0$ , তাহলে তাদের গসাগু হবে বড় সংখ্যা ( $A$ )।

ভিত্তি ০২। যদি কোন সংখ্যাই $0$ না হয়, তাহলে $GCD(A, B) = GCD(B, A mod B)$ ।

আরেকটু সহজভাবে বোঝার চেষ্টা করা যাক। ওপরের উদাহরণটাই নেয়া যাক। আমরা বের করতে চাচ্ছি $GCD(66, 36)$ এর মান।

যেহেতু কোন সংখ্যাই ০ নয়, তাই দ্বিতীয় ভিত্তি অনুসারে $GCD(A, B) = GCD(B, A mod B)$ । এখন মডুলার অ্যারিদমেটিক সম্পর্কে খুব সামান্য জানতে হবে। $C = A mod B$ মানে হলো $A$ কে $B$ দিয়ে ভাগ করলে $C$ পাওয়া যায়। যেমন, $14 mod 4 = 2, 18 mod 6 = 0$ ।

তাহলে, $GCD(66, 36) = GCD(36, 66 mod 36) = GCD(36, 30)$

এবারও কোন সংখ্যা $0$ হয় নি। আবারও দুই নম্বরে চলে গেলাম।

$GCD(66, 36) = GCD(36, 30)$

$\implies GCD(30, 36 mod 30) = GCD(30, 6)$

$\implies GCD(6, 30 mod 6) = GCD(6, 0)$

এখন যেহেতু একটি সংখ্যা $0$ হয়ে গেছে, তাই আমরা প্রথম ভিত্তিতে চলে গেলাম।

$GCD(6, 0) = 6$ ।

এটি কীভাবে কাজ করলো? খুব সংক্ষেপে প্রমাণটা দেখার চেষ্টা করি।

যে দুটো ভিত্তির কথা শুরুতে বলা হলো, তার প্রথমটি প্রমাণ করার চেষ্টা করি শুরুতে। মনে করি $A$ আর $B$ দুটি সংখ্যা, $(A>B)$ যেখানে $B = 0$ । এখন খুব সাধারণ একটা কথা বলি, $24$ এর সবচেয়ে বড় গুণনীয়ক কোনটি? $24$ । তার মানে একটা সংখ্যার সবচেয়ে বড় উৎপাদক সেটি নিজেই (অবশ্যই সেটি যদি $0$ এর চেয়ে বড় হয়!)। তাহলে $A$ এর সর্বোচ্চ উৎপাদক $A$ । এখন $0$ এর সর্বোচ্চ উৎপাদক কী? চিন্তা করে দেখুন তো, $0$ এর উৎপাদক সকল বাস্তব সংখ্যাই কিনা! $0$ কে যেকোন সংখ্যা দিয়ে ভাগ করলেই কোন ভাগশেষ থাকে না! অর্থাৎ $0$ এর উৎপাদক সব সংখ্যাই। $A$ এর সর্বোচ্চ উৎপাদক $A, 0$ এর সর্বোচ্চ উৎপাদক সব সংখ্যাই, তাহলে এদের দুজনেরই উৎপাদক, এমন সবচেয়ে বড় সংখ্যাটিও $A$ । সহজ কথায় এদের গসাগু $A$

তারমানে আমরা বুঝলাম, $GCD(A, 0) = A$ । এখন যদি প্রশ্ন করা হয় $A = 0$ হলে কী হবে? একটু চিন্তা করলেই বুঝতে পারবেন, এর উত্তরটা আসলে অসংজ্ঞায়িত!

এবার দ্বিতীয় ক্ষেত্রে আসা যাক। শুরুতেই মূল প্রমাণটা করব না। অন্য একটা জিনিস প্রমাণ করে ভোজবাজির মতো আসল জায়গায় চলে যাবো। আমরা প্রমাণ করবো $GCD(A, B) = GCD(B, A-B)$ ; যদি $A \geq B$ হয়।

মনে করি, $C = A - B \implies B + C = A$ ।

প্রথম অংশঃ

$GCD(A, B)$ যেহেতু $A$ এর উৎপাদক, তাই $x.GCD(A, B) = A$ (যেখানে $x$ যেকোন সংখ্যা)

$GCD(A, B)$ যেহেতু $B$ এরও উৎপাদক, তাই, $y.GCD(A, B) = B$ (যেখানে $y$ যেকোন সংখ্যা)

দুটি অংশ বিয়োগ করে পাই, $(x-y).GCD(A, B) = A - B \implies (x-y).GCD(A, B) = C$ ; তার মানে $GCD(A, B), C$ এরও উৎপাদক।

দ্বিতীয় অংশঃ

$GCD(B, C)$ যেহেতু $B$ এর উৎপাদক, তাই, $m.GCD(B, C) = B$ (যেখানে $m$ যেকোন সংখ্যা)

$GCD(B, C)$ যেহেতু $C$ এরও উৎপাদক, তাই, $n.GCD(B, C) = C$ (যেখানে $n$ যেকোন সংখ্যা)

দুটি অংশ যোগ করে পাই, $(m+n).GCD(B, C) = B + C \implies (m+n).GCD(B, C) = A$ ; তার মানে $GCD(A, B), A$ এরও উৎপাদক।

শেষ অংশঃ

আমরা জানি, $GCD(A, B), B$ এর উৎপাদক। আবার প্রথম অংশ থেকে পাই, $GCD(A, B), C$ এর উৎপাদক। তাহলে $GCD(A, B), B$ ও $C$ এর সাধারণ উৎপাদক (গরিষ্ঠ কিনা জানা নেই)।

আর আমরা জানি $B, C$ এর সবচেয়ে বড় সাধারণ উৎপাদক হল $GCD(B, C)$ । অর্থাৎ,

$GCD(A, B) \leq GCD(B, C)$

আবার, $GCD(B, C), B$ এর উৎপাদক। আবার দ্বিতীয় অংশ থেকে পাই, $GCD(B, C), A$ এর উৎপাদক। তার মানে $GCD(B, C), A$ ও $B$ এর সাধারণ উৎপাদক (এবারও গরিষ্ঠ কিনা জানা নেই)।

আমরা আগে থেকেই জানি, $GCD(A, B)$ হল $A, B$ এর সবচেয়ে বড় উৎপাদক। অর্থাৎ,

$GCD(B, C) \leq GCD(A, B)$ । কী একটা অদ্ভুত সমস্যায় পড়া গেল! দুটি সংখ্যা তুলনা করতে গিয়ে এরকম একটা জায়গায় গিয়ে পৌঁছে গেলাম – $a \geq b$ এবং $b \geq a$ ! একসাথে দুটি কথাই সত্য হওয়ার মানে হলো অবশ্যই $a = b$ ।

তার মানে $GCD(A, B) = GCD(B, A-B)$ এইটুকু আমরা প্রমাণ করতে পারলাম।

কিন্তু আমাদের দ্বিতীয় ভিত্তি তো একটু অন্যরকম ছিল। বলা ছিল $GCD(A, B) = GCD(B, A mod B)$ । এবার একটু ঠাণ্ডা মাথায় চিন্তা করা যাক। $A$ থেকে বারবার $B$ বিয়োগ করতে থাকলে আমরা শেষমেষ কোথায় গিয়ে থামবো? যেমন ধরা যাক, $14$ থেকে বারবার $4$ বিয়োগ করবো, প্রথমে $10$ , এরপর $6$ , এরপর $2$ , আর তো বিয়োগ করা যাচ্ছে না। আর $14 mod 4 = 2$ । তার মানে বারবার বিয়োগ করতে থাকা, আর ভাগশেষ নেওয়া আদতে একই জিনিস!

তার মানে, আমরা শেষমেষ দ্বিতীয় ভিত্তিটিও প্রমাণ করে ফেললাম, $GCD(A, B) = GCD(B, A mod B)$ ।

সি++ এর রিকার্সিভ ফাংশন ব্যবহার করে খুব সহজে এটি ইমপ্লেমেন্ট করা যায়।

        
int calculate_GCD(int a, int b) {
                  
           if (a < b) swap(a,b);
                  
           if (b == 0) return a;
                  
      return calculate_GCD(b,a%b);
                  
}

আচ্ছা, এভাবে $0$ না আসা পর্যন্ত এমনও তো হতে পারে ভাগ করতে করতে বুড়ো হয়ে গেলাম, তবু নিঃশেষে বিভাজ্য হলো না! এজন্য আমাদের সুখবর দিয়ে গেছেন গ্যাব্রিয়েল লামে। ১৮৪৪ সালে তিনি প্রমাণ করে ফেলেছেন, দশমিক সংখ্যায় ছোট সংখ্যায় যতগুলো অংক থাকবে, এই অ্যালগরিদমে ধাপের সংখ্যা তার পাঁচ গুণের বেশি হতে পারবে না। এটিই ছিল আধুনিক “Computational Complexity Theory” এর একটা সূচনা। যারা প্রোগ্রামিং নিয়ে সামান্য পড়াশুনা করেছেন, তারা সম্ভবত টাইম কমপ্লেক্সিটির সাথে পরিচিত হয়ে থাকবেন। সেই ধারণাটি মূলত এখান থেকেই এসেছে।

তবে সি++ প্রোগ্রামিংয়ে আমাদের এই ইমপ্লেমেন্টেশন করার দরকার পড়ে না। লাইব্রেরি ফাংশনের মধ্যে আমাদের জন্য আমাদের জন্য আগে থেকেই ইমপ্লেমেন্ট করা আছে। আমাদের শুধু জানতে হবে কীভাবে আমরা সেই সুবিধাকে কাজে লাগাতে পারি।

        
int g = __gcd(a,b);

আমরা যদি একাধিক সংখ্যার গসাগু বের করতে চাই, তাহলে দুটি করে হিসেব করলেই মূল গসাগু পেয়ে যাবো।

যেমন, তিনটি সংখ্যা $a, b, c$ এর গসাগু হলো $x = gcd(a,b)$ হলে $gcd(a,b,c) = gcd(x,c)$

        
int g = __gcd(a,__gcd(b,c);

Thursday Thoughts

Recent Posts

ইউক্লিডিয়ান অ্যালগরিদম

React

Share with your friends!

Comments

Post a Comment