Como verificar se a raiz quadrada de um número é inteira: 5 métodos em Java

Introdução: o problema que explode o Stack Overflow

Imagine: você está escrevendo um código que processa milhares de números por segundo. Você precisa filtrar aqueles cuja raiz quadrada é um número inteiro (1, 4, 9, 16…). Parece simples, não? É só usar Math.sqrt(), verificar o resto e pronto. Mas não é tão simples assim.

A pergunta «Fastest way to determine if an integer's square root is an integer» no Stack Overflow já acumulou mais de 100.000 visualizações. Por quê? Porque Math.sqrt() é uma operação de ponto flutuante, o que a torna lenta e sujeita a erros de arredondamento. Para números grandes (por exemplo, 2^50), o double pode simplesmente "mentir".

Neste artigo, vamos explorar 5 abordagens em Java: desde a mais ingênua até algoritmos rápidos que usam operações bit a bit e aritmética inteira. Você descobrirá qual método é realmente mais rápido e qual é mais seguro. Vamos lá!

Definição do problema

Precisamos escrever um método boolean isPerfectSquare(long n) que retorna true se n for um quadrado perfeito. Exemplos:

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

Vamos testar com long, já que int é um caso particular e long oferece mais espaço para erros.

Método 1: Ingênuo — Math.sqrt + verificação do resto

A maneira mais simples que vem à mente de um iniciante:

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

Problema nº1: Precisão. Para números maiores que ~2^53 (9.007.199.254.740.991), o double deixa de representar números inteiros com precisão. Exemplo: n = 999999999999999999L — Math.sqrt retornará um resultado incorreto.

Problema nº2: Velocidade. Math.sqrt é uma instrução do processador (FSQRT), mas ainda é mais lenta que operações aritméticas simples.

Quando usar: Apenas para int ou long pequenos (< 10^12), onde a velocidade não é crítica.

Método 2: Raiz quadrada inteira via Newton-Raphson

O método de Newton (Newton-Raphson) é uma forma clássica de calcular a raiz quadrada sem números de ponto flutuante. Refinamos iterativamente a aproximação:

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

O algoritmo converge muito rapidamente — em O(log log n) iterações. Para números até Long.MAX_VALUE, são necessárias apenas 6-8 iterações.

Vantagens: Precisão absoluta para todos os long (até 2^63-1). Não usa double.

Desvantagens: Divisão é uma operação cara. Para números muito pequenos (n < 4), pode-se adicionar uma verificação no início.

Método 3: Busca binária da raiz

Outro algoritmo clássico — procuramos a raiz por busca binária no intervalo [0, n]. Para long, o valor máximo da raiz é 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