algorithm - 用函数式语言实现扩展欧几里德算法

Question

我正在尝试在 OCaml 中实现扩展欧几里德算法，并尝试基本上复制 this Haskell implementation稍作修改(返回 GCD 以及 Bezout 系数)，我写了以下内容。

(* A function to help get the quotient and remainder. *)
let rec quot_help a b q = 
    if (a = b*q) then q
    else if (a > b*q) then quot_help a b (q+1)
    else q-1;;

(* A function to get the quotient and remainder, as a pair. *)
let rec quotrem a b = let q = quot_help a b 0 in (q, a - b*q);; 

(* A helper to the main function. Most of the work is done here.*)    
let rec step a b s t u v =
    if (b = 0) then (a, 1, 0)
    else let (q, r) = quotrem a b in
    step b r u v (s - q*u) (t - q*v);;

let extEuc a b = step a b 1 0 0 1;; 


(* For printing an example. *)
let (q, r) = quotrem 5 3 in Printf.printf "%d, %d" q r;;
print_string "\n";;
let (o1, o2, o3) = extEuc 5 3 in Printf.printf "%d, %d, %d" o1 o2 o3;;

但是，对于 extEuc 的任何输入，这总是打印出 1, 1, 0。我不知道为什么。

我也不明白欧几里德算法在这里是如何工作的。我可以在纸上做欧几里德算法，将一个方程的余数代入另一个方程并收集系数。但是对于我读过的关于欧几里德算法的所有内容，我无法将该过程与在实现该算法的代码中传递的系数联系起来。

Answer 1

如所写，您的 step 函数显式返回所有输入的 (a, 1, 0)。 a 的值是正确的 gcd，但显然 1 和 0 不能是所有情况下的 Bezout 系数。

请注意，您的函数并不总是像您声称的那样返回 (1, 1, 0)。如果这两个数互质(例如 5 和 3)，它就会这样做。但不适用于其他情况:

 # extEuc 55 5;;
 - : int * int * int = (5, 1, 0)

很可能如果您在 b = 0 时修正 step 的值，您将开始获得好的答案。