如何修复Ada递归扩展GCD函数？C版本正常Ada版本输出异常

我需要用Ada语言实现递归版的扩展欧几里得算法，已经写了C和Ada两个逻辑相似的函数，但只有C版本能正常运行。输入参数a=-56、b=15时，C版本输出：GCD=1，x=4，y=15；而Ada版本输出：GCD=1，x=4，y=11，结果不符，需要修复Ada函数。

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;

问题原因 #

核心差异在于C和Ada对负数的除法和取模行为不同：

• C的/是向零取整，%的余数符号与被除数一致；
• Ada的/是向负无穷取整，mod的余数符号与除数一致（且余数非负）。

这种差异导致递归过程中的商和余数计算不一致，最终输出的y值偏离预期。

修复后的Ada代码 #

function extended_gcd(A, B : Integer; X, Y : out Integer) return Integer is
    G : Integer;
    X1, Y1 : Integer;
    C_Quotient : Integer; -- 与C的a/b一致的向零取整商
    C_Remainder : Integer; -- 与C的a%b一致的余数
begin
    if B = 0 then
        X := 1;
        Y := 0;
        return abs A; -- 保证返回正的GCD，符合常规定义
    end if;

    -- 计算C风格的余数和商
    C_Remainder := A rem B; -- Ada的rem与C的%行为一致，余数符号与A相同
    C_Quotient := (A - C_Remainder) / B; -- 推导向零取整的商

    G := extended_gcd(B, C_Remainder, X1, Y1);
    X := Y1;
    Y := X1 - Y1 * C_Quotient;
    return abs G;
end extended_gcd;

修复说明 #

1. 使用A rem B替代A mod B：rem的余数符号与被除数一致，完全匹配C的%行为；
2. 推导向零取整的商：通过(A - C_Remainder) / B计算，确保与C的a/b结果一致；
3. 返回abs G：保证GCD为正数，修正原C代码可能返回负数的问题（符合常规GCD定义）。

测试输入a=-56、b=15时，该代码会输出GCD=1，x=4，y=15，与C版本结果完全一致。

注：扩展欧几里得算法的解不唯一，只要满足a*x + b*y = gcd(a,b)的(x,y)都是正确解。本次修复仅为对齐C版本的输出结果。

内容的提问来源于stack exchange，提问作者Iwjtiwjannaak