โปรแกรม C สำหรับ Extended Euclidean Algorithm

ที่นี่เราจะดู Extended Euclidean Algorithm ที่เขียนด้วย 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

ตัวอย่างโค้ด (C)

#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;
    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