Exponentiation rapide

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

Pour n=8 : appels sur $8,4,2,1,0$. À chaque retour (sauf le cas $0$), un ou deux produits : $x^8=(x^4{)}^2$, etc. — de l'ordre de ${\log }_{2}8=3$ élévations au carré, contre $8$ multiplications pour la version naïve.