floorsqrt

floorsqrt refers to the floor of the square root of a number. In mathematical terms, floor(sqrt(n)) is the greatest integer x such that x^2 ≤ n. The typical domain is nonnegative numbers; for negative inputs, the real square root is not defined, so floorsqrt is usually undefined or triggers an error in software libraries that operate in the reals.

Examples help illustrate the concept: floor(sqrt(0)) = 0, floor(sqrt(1)) = 1, floor(sqrt(2)) = 1, floor(sqrt(9)) = 3, floor(sqrt(15)) = 3, and floor(sqrt(16)) = 4.

Key properties include that floorsqrt is nondecreasing in n and satisfies floor(sqrt(n))^2 ≤ n < (floor(sqrt(n)) + 1)^2. It provides a close integer approximation to the ordinary square root and is useful when only integer results are meaningful.

Computationally, floorsqrt is typically implemented with integer arithmetic to avoid floating-point rounding errors. Common methods include binary search on the range 0 to n, Newton’s method adapted to integers, or digit-by-digit algorithms such as bitwise square-root methods. The usual time complexity is O(log n) with respect to the bit-length of n, and there are optimized variants for large integers.

Applications arise in algorithms and data structures where integer square roots are needed without floating-point precision concerns, including certain number-theory routines, graphical computations, and hashing or indexing schemes. See also integer square root, floor function, and sqrt.