विस्तारित यूक्लिडियन एल्गोरिदम के लिए सी कार्यक्रम?

यहां हम सी का उपयोग करके कार्यान्वित विस्तारित यूक्लिडियन एल्गोरिदम देखेंगे। विस्तारित यूक्लिडियन एल्गोरिदम का उपयोग जीसीडी प्राप्त करने के लिए भी किया जाता है। यह नीचे की तरह x और y के पूर्णांक गुणांक पाता है -

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

यहाँ इस एल्गोरिथम में यह इस तरह के पुनरावर्ती कॉल का उपयोग करके gcd(a, b) के मान को अपडेट करता है - gcd(b mod a, a)। आइए विचार प्राप्त करने के लिए एल्गोरिथम देखें

एल्गोरिदम

EuclideanExtended(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