Search code examples
ada

How to write Recursive GCD program in Ada?

I need Recursive extended Gcd in ADA. I have two similar functions in C and Ada, but only C works. How to fix it?

C:

int extended_gcd(int a, int b, int* x, int* y) {
if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
}
int x1, y1;
int g = extended_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - y1 * (a / b);

return g; }

ADA:

function extended_gcd(A,B: Integer; X,Y: out Integer) return Integer is 
        G :Integer;
    X1,Y1 :Integer;
begin
    if B = 0 then 
        X := 1;
        Y := 0;
        return A;
    end if;     

    G := extended_gcd(B,A mod B,X1,Y1);
    X := Y1;
    Y := X1 - Y1 * (A/B);
    return G;
end extended_gcd;

Input a = -56,b= 15

C output: 1, x = 4,y = 15

ADA output: 1 x = 4, y = 11

Solution

  • The C % operator is the remainder operator, not modulo. The equivalent Ada operator is rem, not mod. Try using rem instead of mod, then you should get the same results.