Comment vérifier si la racine carrée d'un nombre est un entier : 5 méthodes en Java

Introduction : le problème qui fait exploser Stack Overflow

Imaginez : vous écrivez un code qui traite des milliers de nombres par seconde. Vous devez filtrer ceux dont la racine carrée est un entier (1, 4, 9, 16…). Rien de compliqué, semble-t-il ? Vous prenez Math.sqrt(), vous vérifiez le reste, et le tour est joué. Mais ce n'est pas si simple.

La question « Fastest way to determine if an integer's square root is an integer » sur Stack Overflow a déjà accumulé plus de 100 000 vues. Pourquoi ? Parce que Math.sqrt() est une opération en virgule flottante, donc lente et sujette aux erreurs d'arrondi. Pour les grands nombres (par exemple, 2^50), le type double peut tout simplement « mentir ».

Dans cet article, nous allons analyser 5 approches en Java : de la plus naïve aux algorithmes rapides qui utilisent des opérations binaires et l'arithmétique entière. Vous découvrirez quelle méthode est réellement la plus rapide et laquelle est la plus sûre. C'est parti !

Énoncé du problème

Nous devons écrire une méthode boolean isPerfectSquare(long n) qui retourne true si n est un carré parfait (perfect square). Exemples :

\n
• isPerfectSquare(25) → true (5*5)
\n
• isPerfectSquare(26) → false
\n
• isPerfectSquare(0) → true (0*0)
\n
• isPerfectSquare(1) → true
\n

Nous allons tester avec long, car int est un cas particulier, et long offre plus de marge pour les erreurs.

Méthode 1 : Naïve — Math.sqrt + vérification du reste

La méthode la plus simple qui vient à l'esprit d'un débutant :

public static boolean isPerfectSquareSqrt(long n) {\n    if (n < 0) return false;\n    double sqrt = Math.sqrt(n);\n    long floorSqrt = (long) sqrt;\n    return floorSqrt * floorSqrt == n;\n}\n

Problème n°1 : Précision. Pour les nombres supérieurs à ~2^53 (9 007 199 254 740 991), le type double ne peut plus représenter exactement les entiers. Exemple : n = 999999999999999999L — Math.sqrt retournera un résultat incorrect.

Problème n°2 : Vitesse. Math.sqrt est une instruction processeur (FSQRT), mais elle reste plus lente que de simples opérations arithmétiques.

Quand l'utiliser : Uniquement pour les int ou les petits long (< 10^12), lorsque la vitesse n'est pas critique.

Méthode 2 : Racine carrée entière via Newton-Raphson

La méthode de Newton (Newton-Raphson) est une façon classique de calculer une racine carrée sans nombres à virgule flottante. On affine l'approximation de manière itérative :

public static boolean isPerfectSquareNewton(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long x = n;\n    long y = (x + 1) / 2;\n    while (y < x) {\n        x = y;\n        y = (y + n / y) / 2;\n    }\n    return x * x == n;\n}\n

L'algorithme converge très rapidement — en O(log log n) itérations. Pour les nombres allant jusqu'à Long.MAX_VALUE, seules 6 à 8 itérations sont nécessaires.

Avantages : Précision absolue pour tous les long (jusqu'à 2^63-1). N'utilise pas de double.

Inconvénients : La division est une opération coûteuse. Pour les très petits nombres (n < 4), on peut ajouter une vérification au début.

Méthode 3 : Recherche binaire de la racine

Un autre algorithme classique — on cherche la racine par recherche binaire dans l'intervalle [0, n]. Pour un long, la valeur maximale de la racine est 3 037 000 499 (sqrt(Long.MAX_VALUE)).

public static boolean isPerfectSquareBinary(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long low = 1;\n    long high = 3037000499L; // sqrt(Long.MAX_VALUE)\n    while (low <= high) {\n        long mid = (low + high) >>> 1;\n        long square = mid * mid;\n        if (square == n) return true;\n        else if (square < n) low = mid + 1;\n        e