(* Exponentiation rapide

   variante du programme 80 page 328 pour un type quelconque *)

module Exponentiation(X: sig
  type t
  val one: t
  val mul: t -> t -> t
end) = struct

  let rec exp x n =
    if n = 0 then
      X.one
    else
      let r = exp (X.mul x x) (n / 2) in
      if n mod 2 = 0 then r else X.mul x r

end

(* test *)

module E =
  Exponentiation(struct type t = int let one = 1 let mul = ( * ) end)

let () =
  assert (E.exp 2 4 = 16);
  assert (E.exp 1 15 = 1);
  assert (E.exp 2 15 = 32768)

This document was generated using caml2html