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
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.