C प्रोग्राम: विस्तारित यूक्लिडियन एल्गोरिदम

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

a*x + b*y = gcd(a,b)

यहां इस एल्गोरिदम में यह पुनरावर्ती कॉल का उपयोग करके 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  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