Racine $k$-ème entière

On garde l'invariant du cours, $I(g,d):g^k\le a<d^k$. Comme $k\ge 2$, la racine est inférieure à $\sqrt{a}<3037000500$ : on part de $g=0$ et $d=\min (a,3037000499)+1$.

Pour tester $m^k\le a$ sans dépassement, on multiplie $p$ par $m$ tant que $p\le a/m$ (division entière) : si $p>a/m$, alors $p\cdot m>a$, et il est inutile de continuer.

static boolean puissanceInfEgal(long m, int k, long a) { // m >= 1
    long p = 1;
    // I(i) : p = m^i et p <= a
    for (int i = 0; i < k; i++) {
        if (p > a / m) return false;  // p*m > a : donc m^k > a
        p = p * m;
    }
    return true;
}

static long racineK(long a, int k) {
    long g = 0, d = Math.min(a, 3_037_000_499L) + 1;
    // I(g,d) : g^k <= a < d^k
    while (d - g > 1) {
        long m = g + (d - g) / 2;     // g < m < d, donc m >= 1
        if (puissanceInfEgal(m, k, a)) g = m; else d = m;
    }
    return g;                         // g^k <= a < (g+1)^k
}

racineK(1000,3)=10 racineK(999,3)=9 racineK(2^62,2)=2147483648 racineK(Long.MAX,5)=6208 racineK(1,7)=1

On vérifie $6208^5\le 2^{63}-1<6209^5$. Une première version qui calculait $m^k$ directement retournait une valeur fausse pour Long.MAX_VALUE : le produit débordait et devenait négatif. La complexité est $\Theta (k\log a)$.