SqrtnDn

SqrtnDn is a conventional shorthand for the integer square root of n, i.e., the greatest integer whose square does not exceed n. Formally, for n ≥ 0, sqrtnDn(n) = max { k ∈ Z : k^2 ≤ n } = ⌊√n⌋. The function is defined on nonnegative inputs; for negative n the real square root is not defined, and many contexts treat sqrtnDn as undefined or restrict it to nonnegative integers.

In programming and algorithm design, sqrtnDn is used to obtain the floor of the square root without returning a fractional value. It can be computed by several methods, including binary search over the range [0, n], integer-adapted Newton’s method, or fast bitwise algorithms that exploit binary representation. The choice of method depends on the context and performance requirements.

Key properties include monotonicity: if a ≤ b, then sqrtnDn(a) ≤ sqrtnDn(b). The relationship to the real square root is given by ⌊√n⌋ ≤ √n < ⌊√n⌋ + 1, so the difference √n − sqrtnDn(n) lies in [0, 1). This makes sqrtnDn useful in discrete mathematics and algorithmic counting where only whole-number square roots are meaningful.

Examples: sqrtnDn(0) = 0, sqrtnDn(1) = 1, sqrtnDn(2) = 1, sqrtnDn(3) = 1, sqrtnDn(4) = 2, sqrtnDn(17) = 4.

Common applications include grid-based geometry, divisor and factorization routines, and algorithms that operate on square-root bounds in discrete domains. See also floor function and integer square root.