(** Basic arithmetics for ordered euclidian ring. *)

open Scalable

let sign l =
    match sign_b l with
        1 -> [0;1]
      | _ -> [1;1]

(** Greater common (positive) divisor of two non-zero integers.
    @param bA non-zero bitarray.
    @param bB non-zero bitarray.
*)
let rec gcd_b bA bB =
  let r = mod_b (mult_b (sign bA) bA) (mult_b (sign bB) bB)
  in if (>>!) r [] then
      gcd_b (mult_b (sign bB) bB) r
    else bB;;

(** 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 bA non-zero bitarray.
    @param bB non-zero bitarray.
*)
let bezout_b bA bB =
  let rec bezout_b_rec u v r u1 v1 r1=
    if r1 = [] then
      (u, v, add_b (mult_b bA u) (mult_b bB v))
    else
      let q = quot_b r r1 in
      bezout_b_rec u1 v1 r1 (diff_b u (mult_b q u1)) (diff_b v (mult_b q v1)) (diff_b r (mult_b q r1))
  in bezout_b_rec [0;1] [] bA [] [0;1] bB;;