Calculate an Integer Square Root
Finding ⌊√n⌋ without floating point — three approaches, from the naive crawl to the one fast enough to belong in a hot loop.
- What an integer square root actually is
- The naive approach: counting up
- Binary search on the answer
- Newton’s method for integers
- Code in C, Python, and Java
- Complexity and precision pitfalls
- Where this shows up in real systems
What an integer square root actually is
Every introductory math class teaches the square root as a continuous operation: √2 is an irrational number, an infinite decimal that never repeats. Computers, however, spend most of their time working with integers — array indices, pixel coordinates, loop counters, hash buckets — and for those use cases, an irrational answer is worse than useless. What’s actually wanted is the integer square root: the largest whole number whose square does not exceed the input. Formally, for a non-negative integer n, the integer square root is ⌊√n⌋, the floor of the real square root.
This sounds like a rounding detail, but it has real consequences. If you ask for the square root of 10 using floating-point math and then truncate, you might get 3 — which is correct here — but floating-point rounding errors near perfect squares can occasionally push the truncated result one off from the true answer. A method built specifically for integers guarantees correctness in a way that floating-point truncation does not always guarantee at the boundaries.
There’s also a performance angle. On systems without a hardware floating-point unit — many microcontrollers, some embedded chips — converting to floating point, calling a square root routine, and converting back is wasteful when an integer-only algorithm can do the same job using nothing but addition, subtraction, and bit shifts.
The naive approach: counting up
The simplest possible algorithm mirrors how a person might solve it by hand: start at zero, and keep incrementing a candidate value until its square exceeds the target, then step back by one.
# O(sqrt(n)) — fine for small n, painfully slow past a few million def integer_sqrt_naive(n): if n < 0: raise ValueError("square root undefined for negatives") candidate = 0 while (candidate + 1) * (candidate + 1) <= n: candidate += 1 return candidate
This works, and it’s easy to verify by hand. But its running time is proportional to the square root of the input itself — to find the integer square root of one billion, the loop runs roughly 31,623 times. Tolerable for a one-off calculation, but unacceptable inside anything that runs per-frame, per-request, or per-pixel.
Binary search on the answer
A faster strategy notices something the naive loop ignores: the function “is candidate² ≤ n?” is monotonic — it’s true for small candidates and false for large ones, with a single clean crossover point. Whenever a problem has that shape, binary search turns a linear scan into a logarithmic one. Instead of testing every candidate in order, the algorithm keeps a search range and repeatedly tests the midpoint, narrowing the range by half each time.
/* O(log n) — the version worth actually shipping */ unsigned long integer_sqrt(unsigned long n) { if (n < 2) return n; unsigned long lo = 1, hi = n / 2, result = 1; while (lo <= hi) { unsigned long mid = lo + (hi - lo) / 2; /* avoid overflow: compare mid against n/mid instead of mid*mid */ if (mid <= n / mid) { result = mid; lo = mid + 1; } else { hi = mid - 1; } } return result; }
Two details matter more than they look. First, the search range starts at hi = n / 2 rather than n, since for any n greater than 1, the square root can never exceed half the value. Second, the comparison is written as mid <= n / mid instead of the more obvious mid * mid <= n — squaring mid directly risks overflowing the integer type when n is close to the maximum representable value; dividing instead sidesteps that entirely.
Newton’s method for integers
A third approach borrows from numerical analysis. Newton’s method finds roots of a function by starting with a guess and repeatedly refining it using the function’s slope. Applied to f(x) = x² - n, the update rule simplifies to a clean average: x_next = (x + n / x) / 2. Using integer division throughout keeps every intermediate value a whole number, and the sequence converges remarkably fast — typically within a handful of iterations regardless of how large n is.
// O(log log n) in practice — converges fast, needs a careful stopping rule public static long integerSqrt(long n) { if (n < 2) return n; long x = n; long y = (x + 1) / 2; while (y < x) { x = y; y = (x + n / x) / 2; } return x; }
Newton’s method tends to overshoot slightly before settling, so the loop condition y < x — stop once the estimate stops shrinking — is what guarantees the result lands exactly on the floor of the true square root rather than one above it. Omitting that detail is the single most common bug in hand-rolled integer Newton’s-method implementations.
Comparing the three approaches
| Method | Time complexity | Best suited for |
|---|---|---|
| Naive counting | O(√n) | Teaching, tiny inputs, reference tests |
| Binary search | O(log n) | General-purpose, safest against overflow |
| Newton’s method | ≈O(log log n) | Hot loops, large n, when overflow is handled |
In practice, binary search is the version most worth keeping around as a default — it’s simple to reason about, easy to prove correct, and naturally resistant to overflow once the division trick is applied. Newton’s method is faster in raw iteration count, but it demands more care. Many standard libraries use a hybrid: a few Newton iterations to get close, followed by a small correction step to guarantee the exact floor value.
Precision pitfalls worth remembering
- Off-by-one at perfect squares. Test every implementation against inputs like 0, 1, 4, 9, 100, and 10000 — these are exactly where floor-rounding bugs hide.
- Overflow during squaring. Any version that multiplies the candidate by itself needs a type wide enough to hold that product, or a division-based comparison instead.
- Negative input handling. Integer square roots are undefined for negative numbers; decide explicitly whether your function should raise an error, return zero, or return a sentinel value.
- Mixing with floating point. If a result later needs to be compared against a float-based calculation elsewhere in the same system, make sure both paths agree on rounding behavior.
Where this shows up in real systems
Integer square roots are unglamorous but everywhere. Computer graphics code uses them constantly for distance calculations between points — checking collisions, sorting objects by proximity, or computing lighting falloff. Cryptographic libraries use fast integer square root routines as a building block inside primality tests and in implementations of algorithms like the Tonelli-Shanks method for finding modular square roots. Embedded systems without a floating-point unit rely on integer-only routines like the binary search version above simply because there is no hardware alternative.
The broader lesson generalizes past square roots specifically: whenever a problem has a monotonic “is this candidate good enough?” test, binary search on the answer is almost always worth trying before reaching for anything fancier, and Newton’s method is worth reaching for once correctness is nailed down and raw speed actually matters.