Puissance entière et dépassement

Exercice · OCaml (option informatique), chapitre 1 — Découvrir OCaml : expressions, valeurs et types

Énoncé

Écrire une fonction récursive puissance x n calculant $x^{n}$ pour $n \geq 0$ entier (sans l'opérateur **, réservé aux flottants). Expliquer ce qu'on observe pour de grandes valeurs, et le lien avec l'atelier en ligne.

Corrigé

let rec puissance x n =
  if n = 0 then 1
  else x * puissance x (n - 1)

Le cas de base $n = 0$ renvoie 1 (convention $x^{0} = 1$ ) ; chaque appel décrémente n, donc le calcul s'arrête. Pour de grandes valeurs (p. ex. puissance 2 64), le résultat déborde la capacité du type int et l'on obtient une valeur erronée (souvent négative) : c'est le dépassement de capacité. Dans l'atelier du navigateur, où int est sur 32 bits, ce débordement survient bien plus tôt (dès puissance 2 31 environ) que sur un OCaml natif 63 bits.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.