(* Exponentiation rapide *) let rec puissance x n= if n mod 2 =0 then if n=0 then 1 else let a=puissance x (n/2) in a*a else let a=puissance x (n/2) in x*(a*a) ;; trace "puissance";; puissance 2 10;; (* toujours le même, mais en itératif*) (*un invariant pour une preuve de programme est le triplet (pui,base,n) qui vérifie tout du long pui*base^n=x^n *) let puissiter x exp= let pui = ref 1 and base = ref x and n = ref exp in while !n>0 do if !n mod 2=0 then begin n:=!n/2; base:=!base*(!base) end else begin n:=!n-1; pui:=!pui*(!base) end done; !pui ;; (* Exponentiation rapide avec décomposition binaire *) let rec intabin n l=match n with |0->l |n-> if n mod 2= 0 then intabin (n/2) (0::l) else intabin ((n-1)/2) (1::l) ;; let i_bin n= if n=0 then [0] else intabin n [];; let rec puissance x l=match l with |([]|[0])->1 |0::m->puissance (x*x) m |1::m->x*puissance (x*x) m ;; let vrai x l=puissance x (List.rev l);;