Racine carrée entière

• Initialisation $r=0$ ($0\le n$). Progression : $r^2\le n\wedge (r+1{)}^2\le n\Rightarrow (r+1{)}^2\le n$, on incrémente $r$. Arrêt : $(r+1{)}^2>n$, donc $r=\lfloor \sqrt{n}\rfloor$. La boucle fait $\lfloor \sqrt{n}\rfloor$ tours : $\Theta (\sqrt{n})$.

static int racineLineaire(int n) {    // n ≥ 0
    int r = 0;                        // r² ≤ n
    while ((r + 1) * (r + 1) <= n)    // r² ≤ n et (r+1)² ≤ n
        r = r + 1;                    // r² ≤ n
    return r;                         // r² ≤ n < (r+1)²
}

• Initialisation : $g=0$, $d=n+1$ ($0\le n<(n+1{)}^2$). Arrêt : $d-g=1$, alors $g^2\le n<(g+1{)}^2$. Progression, avec $m=\lfloor (g+d)/2\rfloor$ qui vérifie $g<m<d$ tant que $d-g\ge 2$ : $I(g,d)\wedge m^2\le n\Rightarrow I(m,d)$ et $I(g,d)\wedge m^2>n\Rightarrow I(g,m)$. Le variant $d-g$ est au moins divisé par deux à chaque tour : $\Theta (\log n)$.

static int racineDicho(int n) {       // n ≥ 0
    long g = 0, d = (long) n + 1;     // I(g,d) : g² ≤ n < d²
    while (d - g != 1) {              // I(g,d) et d - g ≥ 2
        long m = (g + d) / 2;         // g < m < d
        if (m * m <= n) g = m;        // I(m,d)
        else d = m;                   // I(g,m)
    }                                 // g² ≤ n < (g+1)²
    return (int) g;
}

• Pour $n=2^{31}-1$, $d=n+1$ dépasse déjà la capacité d'un int, et $m^2$ peut atteindre $2^{60}$. Avec des long, racineDicho(2147483647) retourne bien $46340$ ; la version linéaire, elle, déborde sur (r + 1) * (r + 1) pour ce $n$.