(* Calcul modulo m *)

module Modulo(M: sig val m: int end) :
sig
  type t = private int
  val zero: t
  val one: t
  val of_int: int -> t
  val add: t -> t -> t
  val sub: t -> t -> t
  val mul: t -> t -> t
  val div: t -> t -> t
end =
struct

  open M

  let () = assert (0 < m && m <= max_int/2 + 1)

  type t = int

  (* sera utile pour l'exercice 10.12 *)
  let zero = 0
  let one = 1

  let of_int x =
    let r = x mod m in if r < 0 then r + m else r

  let add x y =
    let r = x + y in if r >= m then r - m else r

  let sub x y =
    let r = x - y in if r < 0 then r + m else r

  let mul x y =
    let r = ref 0 in
    for i = Sys.word_size - 4 downto 0 do
      r := add !r !r;
      if x land (1 lsl i) <> 0 then r := add !r y
    done;
    !r

  let rec extended_gcd u v =
    if v = 0 then
      1, 0, u
    else
      let x,y,g = extended_gcd v (u mod v) in
      y, x - y*(u/v), g

  let div x y =
    let u, _, g = extended_gcd y m in
    if g <> 1 then invalid_arg "div";
    mul x (of_int u)

end

(* Notes :

   - Écrire ce code sous la forme d'un foncteur permet de garantir que le
     même entier m est utilisé dans toutes les opérations. Si m était
     passé en argument à chaque opération, le risque serait grand de ne
     pas être cohérent.

   - Faire du type t un type abstrait (ou comme ici un type privé) permet
     de garantir l'invariant 0 <= x < m pour toute valeur x du type t.
*)


(* tests *)

let () =
  let module M = Modulo(struct let m = 5003 end) in
  let open M in
  for x = 0 to 100 do for y = 0 to 100 do
    assert (add (of_int x) (of_int y) = of_int (x + y));
    assert (sub (of_int x) (of_int y) = of_int (x - y));
    assert (mul (of_int x) (of_int y) = of_int (x * y));
    if y <> 0 then
      assert (mul (of_int y) (div (of_int x) (of_int y)) = of_int x);
  done done

This document was generated using caml2html