Dichotomiser sur la réponse : la racine carrée entière

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 15 — Diviser pour régner

Énoncé

Écrire, avec spécification, terminaison et correction, une fonction rendant $⌊ n ⌋$ sans employer de flottants. Où se cache le débordement ?

Corrigé

La propriété « $r^{2} \leq n$ » est monotone en $r$ : vraie jusqu'à un seuil, fausse ensuite. On dichotomise sur ce seuil.


(* Renvoie le plus grand r tel que r*r <= n, c'est-à-dire floor(sqrt n).
   Précondition : n >= 0. Aucun flottant, aucun débordement.
   Complexité : Theta(log n). *)
let racine n =
  let bas = ref 0 and haut = ref (n + 1) in
  (* INVARIANT : bas*bas <= n < haut*haut, et bas < haut. *)
  while !haut - !bas > 1 do
    let m = !bas + (!haut - !bas) / 2 in
    if m <= n / m then bas := m else haut := m       (* PAS m * m <= n *)
  done;
  !bas

Terminaison. Variant : $haut - bas$ . Comme $bas < m < haut$ dès que l'écart dépasse $1$ , l'affectation réduit strictement l'écart. Il faut $Θ (lo g n)$ tours.

Correction. L'invariant tient à l'initialisation : $0 \leq n$ et $n < (n + 1)^{2}$ pour $n \geq 0$ . Il est préservé par construction, puisqu'on remplace l'une des bornes par $m$ du bon côté du test. À la sortie, $haut = bas + 1$ et $bas^{2} \leq n < (bas + 1)^{2}$ : c'est la définition de $⌊ n ⌋$ .

Le débordement, et il est où l'on ne l'attend pas. La forme naturelle du test est m * m <= n. Or $m$ vaut environ $n /2$ au premier tour : le produit $m^{2}$ approche $n^{2} /4$ , qui déborde bien avant $n$ . Mesuré en OCaml, dont les entiers font $63$ bits (max_int $= 4611686018427387903$ ) :

$n$	test `m * m <= n`	test `m <= n / m`
$1 0^{6}$	$1000$	$1000$
$999999999$	$31622$	$31622$
$999999999999$	$101455818926$	$999999$
$1 0^{15}$	$221360854171413$	$31622776$

La première divergence apparaît à $n = 2^{32} = 4294967296$ , valeur trouvée en balayant les puissances de deux. Au-delà, la version naïve rend des résultats absurdes — un « $⌊ n ⌋$ » plus grand que $n$ — sans le moindre signalement.

Le remède. Écrire m <= n / m : la division entière ne déborde jamais, et le test est équivalent pour $m \geq 1$ . C'est le même geste qu'au chapitre chap:langage-c — x <= INT8_MAX - y plutôt que x + y <= INT8_MAX : on réécrit le test pour que l'expression testée ne puisse pas déborder avant d'être testée.

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.