Recherche d'un seuil monotone

let premier_vrai p a b =
  let g = ref a and d = ref b in
  while !g < !d do
    let m = (!g + !d) / 2 in
    if p m then d := m else g := m + 1
  done;
  !g

(* Plus grand r tel que r*r <= n : le seuil où (m+1)^2 > n commence. *)
let racine n =
  if n = 0 then 0
  else premier_vrai (fun m -> (m + 1) * (m + 1) > n) 0 n

premier_vrai encapsule une fois pour toutes le schéma de dichotomie sur un prédicat monotone. On l'instancie avec le prédicat « $(m+1{)}^2>n$ » (croissant) : son plus petit point vrai est précisément $\lfloor \sqrt{n}\rfloor$. C'est la puissance des fonctions d'ordre supérieur : un algorithme, mille usages.