এখানে আমরা এক্সটেনডেড ইউক্লিডিয়ান অ্যালগরিদমটি C-তে ইমপ্লিমেন্ট করব। এক্সটেনডেড ইউক্লিডিয়ান অ্যালগরিদমও GCD বের করতে ব্যবহৃত হয়। এটি x এবং y-এর ইন্টিজার কোএফিশিয়েন্ট বের করে নিচের মত করে −
ax + by = 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
উদাহরণ
#includeint 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
