Racine carrée entière par dichotomie

Exercice · OCaml (option informatique), chapitre 10 — Recherche et dichotomie

Énoncé

Écrire racine n ( $n \geq 0$ ), le plus grand $r$ tel que $r^{2} \leq n$ , en $Θ (lo g n)$ par dichotomie (à comparer au $Θ (n)$ du chapitre 4).

Corrigé

let racine n =
  let g = ref 0 and d = ref n in
  while !g < !d do
    let m = (!g + !d + 1) / 2 in   (* milieu « par excès » *)
    if m * m <= n then g := m
    else d := m - 1
  done;
  !g

On cherche le plus grand m avec m<em>m <= n. Invariant : !g </em> !g <= n (g est réalisable) et la réponse est dans [g, d]. Le milieu par excès (+1) est nécessaire : avec g := m et un milieu par défaut, on bouclerait sans fin quand d = g + 1. Variant : d - g. Coût $Θ (lo g n)$ . racine 10 $= 3$ .

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.