Реализация расширенного евклидова алгоритма на функциональном языке

Question

Я пытаюсь реализовать расширенный евклидов алгоритм в OCaml и, пытаясь в основном скопировать эту реализацию Haskell с небольшой модификацией (возвращая GCD, а также коэффициенты Безу), я написал следующее.

(* 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;;

Однако, это всегда печатает 1, 1, 0 для любых входов в extEuc.Я не могу понять, почему.

Я также не могу понять, как работает Евклидов алгоритм.Я могу сделать евклидов алгоритм на бумаге, подставляя остаток от одного уравнения в другое и собирая коэффициенты.Но из всего, что я прочитал о евклидовом алгоритме, я не могу связать этот процесс с коэффициентами, которые передаются в коде, который реализует алгоритм.

Answer 1

Как написано, ваша step функция явно возвращает (a, 1, 0) для всех входных данных.Значение a является правильным gcd, но, очевидно, 1 и 0 не могут быть коэффициентами Безу для всех случаев.

Обратите внимание, что ваша функция не всегда возвращает (1, 1, 0), так как выЗапрос.Это происходит, если два числа относительно простые (например, 5 и 3).Но не для других случаев:

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

Скорее всего, если вы исправите значение step при b = 0, вы начнете получать хорошие ответы.