Racine carrée entière par dichotomie

Recherche et dichotomie · niveau 3 (difficile)

É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*m <= n. Invariant : !g * !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$ .

Énoncé

Corrigé

Exercices semblables