floorsqrtn

floorsqrtN is the mathematical function that returns the floor of the square root of a non-negative integer N. Formally, floorsqrtN(N) is the greatest integer x such that x^2 is less than or equal to N. In real analysis terms, it is the integer part of sqrt(N). For negative N, the floor of the real square root is not defined.

Key properties include monotonicity (if a <= b, then floorsqrtN(a) <= floorsqrtN(b)) and the identity floorsqrtN(N^2) = N for non-negative N. The value grows as N increases, and floorsqrtN(N) is always nonnegative.

Computing floorsqrtN typically uses one of several algorithms. A common approach is binary search on the interval [0, N], updating the search range based on whether mid^2 <= N. To avoid overflow when N is large, the check is often performed as mid <= N / mid. Alternative methods include Newton’s iteration, which refines an estimate x by x = floor((x + floor(N / x)) / 2) until convergence, and digit-by-digit methods that simulate long division to produce the integer square root. Some optimizations exist for fixed word sizes, using bit-shifting tricks to narrow the search space quickly.

Common usage includes algorithms that require integer square roots, such as lattice point counting, geometry problems, and certain cryptographic or numerical routines. In many programming languages, a built-in function like isqrt or equivalent provides floorsqrtN for non-negative integers.

Example values: floorsqrtN(0) = 0, floorsqrtN(1) = 1, floorsqrtN(15) = 3, floorsqrtN(256) = 16.