(* Exponentiation rapide

   variante du programme 80 page 328 *)

let rec exp x n =
  if n = 0 then
    1
  else
    let r = exp x (n / 2) in
    if n mod 2 = 0 then r * r else x * r * r

(* pas de différence d'efficacité : le nombre d'étapes est toujours le même
   (log n), ainsi que le nombre de multiplications (on fait la multiplication
   après au lieu de la faire avant) *)

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

This document was generated using caml2html