Integer Square Roots and Perfect Power Detection

Q: Why filter modulo 64 rather than a prime?

Because the reduction is a bitwise AND, making it the cheapest possible filter, and because 64 is a strong filter in its own right — only 12 of its 64 classes contain squares. Prime moduli are used for the subsequent filters, where independence matters more than reduction cost.

Q: How do I compute an integer k-th root?

By the same Newton iteration generalised: x ← ((k−1)x + n/x^(k−1))/k, with an initial estimate from the bit length. Convergence is still quadratic, but each step is more expensive, so a good initial estimate matters more than in the square case.

Q: Is a perfect square always detected by the filters?

Yes — the filters never produce false negatives, only false positives. A genuine square passes every residue test by construction, so the filters can only send non-squares through to the exact check, never reject a real square.

Executive summary

Cheap rejection first, expensive confirmation second

The integer square root ⌊√n⌋ is computed by a Newton iteration carried out entirely in integers, converging quadratically from a good initial estimate. Testing whether n is a perfect square, however, should almost never begin with a square root: a handful of modular residue filters reject well over 99% of non-squares at negligible cost, so the expensive exact computation runs only on genuine candidates.

Learning objectives

Implement an integer Newton iteration with a correct termination condition.
Construct residue filters and quantify their rejection rate.
Detect perfect powers by bounding the possible exponents.
Recognise prime powers, and explain why this matters for factoring.

Section 01Integer square root by Newton's method

AlgorithmInteger square rootin: n ≥ 0 → out: ⌊√n⌋, exactly

If n = 0 return 0. Form an initial estimate x ← 2^⌈b/2⌉, where b is the bit length of n. A shift, not a floating-point square root — doubles lose accuracy above 2⁵³.
Set y ← ⌊(x + ⌊n/x⌋)/2⌋.
If y ≥ x, return x. Termination test: the iteration has stopped decreasing.
Set x ← y and return to step 2.

Never trust a floating-point square root

For n above 2⁵³ a double cannot represent n exactly, so floor(sqrt(n)) may be off by one — and off by one is precisely the error that makes a perfect square look imperfect. Use floating point only to form an initial estimate, and always finish in exact integer arithmetic.

Section 02Residue filters for square detection

Squares occupy only a small fraction of residue classes. Modulo 64 there are just 12 possible values of a square; modulo 63, 65 and 11 the fractions are similarly small. Combining a few such filters rejects the overwhelming majority of non-squares with a single table lookup each.

12 / 64square residues mod 64

> 99%non-squares rejected by four filters

O(1)cost per filter

AlgorithmPerfect square testin: n → out: whether n is a perfect square, and its root

Reject immediately if n < 0.
Look up n mod 64 in a 64-entry bit table; if absent, return false.
Repeat with moduli 63, 65 and 11. Chosen so that 63 · 65 · 11 is coprime to 64, maximising independence.
Compute s ← ⌊√n⌋ exactly.
Return true if and only if s² = n, and return s.

This pattern — cheap probabilistic rejection followed by exact confirmation — recurs throughout the subject. It is the same structure as a compositeness test followed by a primality proof.

Section 03Perfect powers and prime powers

If n = m^k with m ≥ 2, then k ≤ log₂ n. Only prime exponents need testing, since a composite exponent factors through a prime one. That bounds the search to a short list.

AlgorithmPerfect power detectionin: n ≥ 2 → out: (m, k) with n = m^k, or none

For each prime k ≤ log₂ n:
Compute the integer k-th root m by Newton's method for k-th roots.
If m^k = n, return (m, k). Recurse on m if a fully reduced base is required.
Return “not a perfect power”.

Why factoring code tests this first

Several major algorithms — Pollard’s ρ, the elliptic curve method, the quadratic sieve — behave badly or fail outright on perfect powers, and the AKS primality test requires the input not to be one. Perfect power detection is cheap and is therefore run as an unconditional first step, before any serious factoring effort begins.

Prime power detection follows: n is a prime power exactly when it is either prime, or a perfect power m^k whose base m is itself a prime power. The recursion terminates quickly because the exponent shrinks by at least a factor of 2 each time.

ReferenceFrequently asked questions

Why filter modulo 64 rather than a prime?

Because the reduction is a bitwise AND, making it the cheapest possible filter, and because 64 is a strong filter in its own right — only 12 of its 64 classes contain squares. Prime moduli are used for the subsequent filters, where independence matters more than reduction cost.

How do I compute an integer k-th root?

By the same Newton iteration generalised: x ← ((k−1)x + n/x^(k−1))/k, with an initial estimate from the bit length. Convergence is still quadratic, but each step is more expensive, so a good initial estimate matters more than in the square case.

Is a perfect square always detected by the filters?

Yes — the filters never produce false negatives, only false positives. A genuine square passes every residue test by construction, so the filters can only send non-squares through to the exact check, never reject a real square.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.