(** Basic arithmetics with built-in integers *)
(**#use "builtin.ml";;**)
open Builtin


(* Greater common divisor and smaller common multiple
   implemetations.
*)

(** Greater common (positive) divisor of two non-zero integers.
    @param a non-zero integers
    @param b non-zero integer
*)
let rec gcd a b =
  let r = modulo (sign a*a) (sign b*b)
  in if r > 0 then
      gcd (sign b *b) r
    else b;;

(* Extended Euclidean algorithm. Computing Bezout Coefficients. *)

(** Extended euclidean division of two integers NOT OCAML DEFAULT.
    Given non-zero entries a b computes triple (u, v, d) such that
    a*u + b*v = d and d is gcd of a and b.
    @param a non-zero integer
    @param b non-zero integer.
*)

let rec bezout a b =
  let rec bezout_rec u v r u1 v1 r1=
    if r1 = 0 then
      (u, v, a*u + b*v)
    else
      let q = r/r1 in
      bezout_rec u1 v1 r1 (u-q*u1) (v-q*v1) (r-q*r1)
  in bezout_rec 1 0 a 0 1 b;;