CODEWITHSUNDEEP
algorithmocaml
Addem
Addem

Reputation: 3929

Implementing the Extended Euclidean Algorithm in a functional language

I'm trying to implement the Extended Euclidean Algorithm in OCaml and, trying to basically copy this Haskell implementation with slight modification (returning the GCD as well as the Bezout coefficients), I wrote the following. 

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

However, this always prints out 1, 1, 0 for any inputs to extEuc. I can't figure out why.

I also can't understand how the Euclidean Algorithm works here. I can do the Euclidean algorithm on paper, substituting the remainder from one equation to another and collecting coefficients. But for all that I've read on the Euclidean Algorithm, I can't connect that process to the coefficients that are getting passed around in code that implements the algorithm.

Upvotes: 1

Views: 675

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

As written, your step function explicitly returns (a, 1, 0) for all inputs. The value of a is the correct gcd, but obviously 1 and 0 can't be the Bezout coefficients for all cases.

Note that your function does not always return (1, 1, 0) as you claim. It does if the two numbers are relatively prime (like 5 and 3). But not for other cases:

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

Most likely if you fix up the value of step when b = 0, you'll start getting good answers.

Upvotes: 1

Related Questions