How to Check if a Number's Square Root is an Integer: 5 Methods in Java

Introduction: The Problem That Blows Up Stack Overflow

Imagine: you're writing code that processes thousands of numbers per second. You need to filter out those whose square root is an integer (1, 4, 9, 16…). Seems simple, right? Just use Math.sqrt(), check the remainder, and you're done. But it's not that straightforward.

The question «Fastest way to determine if an integer's square root is an integer» on Stack Overflow has already gathered over 100,000 views. Why? Because Math.sqrt() is a floating-point operation, meaning it's slow and prone to rounding errors. For large numbers (e.g., 2^50), double can simply "lie".

In this article, we'll break down 5 approaches in Java: from the most naive to fast algorithms that use bitwise operations and integer arithmetic. You'll learn which method is actually faster and which is safer. Let's go!

Problem Statement

We need to write a method boolean isPerfectSquare(long n) that returns true if n is a perfect square. Examples:

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

We will test on long, since int is a special case, and long provides more room for errors.

Method 1: Naive — Math.sqrt + Remainder Check

The simplest way that comes to a beginner's mind:

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

Problem #1: Precision. For numbers larger than ~2^53 (9,007,199,254,740,991), double can no longer accurately represent integers. Example: n = 999999999999999999L — Math.sqrt will return an incorrect result.

Problem #2: Speed. Math.sqrt is a CPU instruction (FSQRT), but it's still slower than simple arithmetic operations.

When to use: Only for int or small long values (< 10^12) where speed is not critical.

Method 2: Integer Square Root via Newton-Raphson

Newton's method (Newton-Raphson) is a classic way to compute a square root without floating-point numbers. Iteratively refine the approximation:

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

The algorithm converges very quickly — in O(log log n) iterations. For numbers up to Long.MAX_VALUE, only 6-8 iterations are needed.

Pros: Absolute precision for all long values (up to 2^63-1). Does not use double.

Cons: Division is an expensive operation. For very small numbers (n < 4), you can add a check at the beginning.

Method 3: Binary Search for the Root

Another classic algorithm — we search for the root using binary search on the interval [0, n]. For long, the maximum root value is 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