Introduction

Determining whether an integer is a perfect square sounds trivial -- just take the square root and check if it is a whole number. But this naive approach breaks down for large numbers where floating-point precision fails silently, and in performance-critical code where you may need to check millions of candidates. Understanding the fast paths and their tradeoffs is essential for number theory problems, competitive programming, and any system that deals with large integer arithmetic.

The Naive Approach and Why It Fails

The most obvious method is to compute the floating-point square root and check if it is an integer:

1import math
2
3def is_perfect_square_naive(n):
4    if n < 0:
5        return False
6    root = math.sqrt(n)
7    return root == int(root)

This works for small numbers, but floating-point arithmetic uses 64-bit doubles, which have about 15-17 significant decimal digits of precision. For numbers larger than roughly 2^53 (about 9 quadrillion), math.sqrt() can return a value that rounds to an integer even when the true root is irrational, or miss a perfect square because the root gets truncated.

# This large number IS a perfect square: (10**15 + 3)**2
n = 1000000000000006000000000000009
print(math.sqrt(n))  # 1e+15 -- lost the "+3" entirely

The lesson is clear: floating-point square roots are unreliable for large integers.

The Correct Approach with Integer Square Root

Python 3.8 introduced math.isqrt(), which computes the exact integer square root using pure integer arithmetic -- no floating-point involved. This is both correct for arbitrarily large numbers and faster than you might expect.

1import math
2
3def is_perfect_square(n):
4    if n < 0:
5        return False
6    root = math.isqrt(n)
7    return root * root == n

The math.isqrt(n) function returns the largest integer r such that r * r <= n. By checking root * root == n, you get an exact answer with no precision loss regardless of how large n is. This should be your default approach in Python.

Newton's Method for Integer Square Root

If you are working in a language without a built-in integer square root, or you need to understand what happens under the hood, Newton's method (also called the Babylonian method) converges quickly to the integer square root.

1def isqrt_newton(n):
2    if n < 0:
3        raise ValueError("Square root not defined for negative numbers")
4    if n == 0:
5        return 0
6    x = n
7    y = (x + 1) // 2
8    while y < x:
9        x = y
10        y = (x + n // x) // 2
11    return x
12
13def is_perfect_square_newton(n):
14    if n < 0:
15        return False
16    root = isqrt_newton(n)
17    return root * root == n

Newton's method converges quadratically, meaning it roughly doubles the number of correct digits with each iteration. For a 64-bit integer, this typically takes about 6 iterations. The key detail is using integer division (//) throughout to avoid any floating-point contamination.

Bit-Level Quick Rejection

Before computing any square root, you can reject many non-squares instantly by examining their low-order bits. Perfect squares have a limited set of possible residues modulo small numbers, and checking these is essentially free.

In hexadecimal (mod 16), perfect squares can only end in 0, 1, 4, or 9. This means 75% of random inputs can be rejected with a single bitwise operation:

1def is_perfect_square_fast(n):
2    if n < 0:
3        return False
4
5    # Quick rejection: check last 4 bits (mod 16)
6    last_hex = n & 0xF
7    if last_hex not in (0, 1, 4, 9):
8        return False
9
10    # Full check with integer square root
11    root = isqrt_newton(n)
12    return root * root == n

You can extend this to mod 64 for even more filtering. Perfect squares mod 64 can only be 0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, or 57. The more residues you pre-check, the fewer numbers reach the expensive square root computation. In practice, the mod 16 check alone eliminates 75% of candidates and costs only a bitwise AND.

Java and C++ Approaches

In Java, the standard approach must work around the same floating-point precision issue:

1public static boolean isPerfectSquare(long n) {
2    if (n < 0) return false;
3
4    // Quick rejection via hex residue
5    long h = n & 0xF;
6    if (h > 9) return false;
7    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8) {
8        long root = (long) Math.sqrt(n);
9        // Check root and neighbors to handle rounding
10        if (root * root == n) return true;
11        root++;
12        return root * root == n;
13    }
14    return false;
15}

The root++ check compensates for Math.sqrt() potentially rounding down. By checking both root and root + 1, you cover the precision gap for large values.

In C++, you can use the same Newton's method approach or rely on floating-point with a neighborhood check:

1#include <cstdint>
2#include <cmath>
3
4bool isPerfectSquare(int64_t n) {
5    if (n < 0) return false;
6    if (n == 0) return true;
7
8    // Quick rejection
9    int64_t h = n & 0xF;
10    if (h > 9) return false;
11
12    int64_t root = static_cast<int64_t>(std::sqrt(static_cast<double>(n)));
13    // Check neighborhood to handle precision loss
14    for (int64_t r = root - 1; r <= root + 1; ++r) {
15        if (r >= 0 && r * r == n) return true;
16    }
17    return false;
18}

Checking a small neighborhood around the floating-point result (root - 1, root, root + 1) is a practical safeguard that costs almost nothing.

Performance Comparison

Here is a rough benchmark comparing the approaches on random 64-bit integers in Python:

1import time, math, random
2
3numbers = [random.randint(1, 10**18) for _ in range(1_000_000)]
4
5# math.isqrt (Python 3.8+)
6start = time.time()
7for n in numbers:
8    r = math.isqrt(n); r * r == n
9print(f"math.isqrt: {time.time() - start:.3f}s")
10
11# math.sqrt (floating point)
12start = time.time()
13for n in numbers:
14    r = math.sqrt(n); r == int(r)
15print(f"math.sqrt: {time.time() - start:.3f}s")
16
17# With quick rejection
18start = time.time()
19for n in numbers:
20    if (n & 0xF) in (0, 1, 4, 9):
21        r = math.isqrt(n); r * r == n
22print(f"isqrt + quick reject: {time.time() - start:.3f}s")

The quick rejection filter saves significant time when most inputs are not perfect squares, because 75% of numbers never reach the square root calculation. The math.isqrt version is both correct and fast, typically only 20-30% slower than the unsafe math.sqrt for 64-bit numbers.

Common Pitfalls

• Trusting floating-point square roots for large numbers: math.sqrt() silently gives wrong answers for integers above 2^53. Always verify with integer multiplication (root * root == n).
• Forgetting negative inputs: Negative numbers cannot be perfect squares. Failing to check n < 0 leads to domain errors or incorrect True results from unsigned overflow in C/C++.
• Integer overflow in the verification step: In languages like C++ or Java, root * root can overflow a 64-bit integer if n is close to the maximum value. Use 128-bit multiplication or restructure the check as root == n / root && n % root == 0.
• Skipping the neighborhood check in Java/C++: A single (long) Math.sqrt(n) can be off by one due to floating-point truncation. Always check root and root + 1 against the original number.
• Over-engineering the bit tricks: The mod 16 quick rejection is nearly free and eliminates 75% of candidates. Adding more modular checks adds complexity for diminishing returns unless you are processing billions of candidates.

Summary

• Use math.isqrt() in Python 3.8+ for a correct, efficient check: r = math.isqrt(n); r * r == n.
• Never rely solely on floating-point math.sqrt() for large integers -- precision loss causes silent wrong answers.
• Newton's method with integer division gives you a portable integer square root in any language.
• A quick mod-16 bit check (n & 0xF) rejects 75% of non-squares before any expensive computation.
• In Java and C++, always check the neighborhood around the floating-point root (root - 1, root, root + 1) to handle rounding errors.
• For most applications, math.isqrt() with an optional bit-level pre-filter gives you the best balance of correctness, speed, and simplicity.