বর্ধিত ইউক্লিডীয় অ্যালগরিদমের জন্য সি প্রোগ্রাম?

এখানে আমরা C ব্যবহার করে বর্ধিত ইউক্লিডীয় অ্যালগরিদম বাস্তবায়িত দেখতে পাব। বর্ধিত ইউক্লিডীয় অ্যালগরিদমও GCD পেতে ব্যবহৃত হয়। এটি নিচের মত x এবং y এর পূর্ণসংখ্যা সহগ খুঁজে পায় −

𝑎𝑥+𝑏𝑦 = gcd(𝑎,𝑏)

এখানে এই অ্যালগরিদমে এটি − gcd(b mod a, a) এর মতো পুনরাবৃত্ত কল ব্যবহার করে gcd(a, b) এর মান আপডেট করে। আসুন ধারণা পেতে অ্যালগরিদম দেখি

অ্যালগরিদম

ইউক্লিডীয় সম্প্রসারিত(a, b, x, y)

begin
   if a is 0, then
      x := 0
      y := 1
      return b
   end if
   gcd := EuclideanExtended(b mod a, a, x1, y1)
   x := y1 – (b/a)*x1
   y := x1
   return gcd
end

উদাহরণ

#include <stdio.h>
int EuclideanExtended(int a, int b, int* x, int* y) {
   if (a == 0) {
      *x = 0;
      *y = 1;
      return b;
   }
   int xtemp, ytemp; // To store results of recursive call
   int res = EuclideanExtended(b % a, a, &xtemp, &ytemp);
   *x = ytemp - (b / a) * xtemp;
   *y = xtemp;
   return res;
}
int main() {
   int x, y;
   int a = 60, b = 25;
   int res = EuclideanExtended(a, b, &x, &y);
   printf("gcd(%d, %d) = %d", a, b, res);
}

আউটপুট

gcd(60, 25) = 5