โปรแกรม C สำหรับอัลกอริธึม Extended Euclidean?

ที่นี่เราจะเห็นอัลกอริทึมแบบยุคลิดแบบขยายที่นำมาใช้โดยใช้ C นอกจากนี้ อัลกอริธึมแบบยุคลิดแบบขยายยังใช้เพื่อรับ GCD ด้วย หาค่าสัมประสิทธิ์จำนวนเต็มของ 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