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. — soit $5$ multiplications : $2$ pour n=1, puis une à chacun des trois niveaux suivants, de l'ordre de ${\log }_{2}n$, contre $8$ pour la version naïve.