800. Square Root to a Stated Precision

Given a whole number n and a digit count d, print the square root of n with exactly d digits after the decimal point.

n = 2, d = 6 -> 1.414214 n = 16, d = 3 -> 4.000 n = 1000000000, d = 6 -> 31622.776602 n = 0, d = 4 -> 0.0000

This is problem 248 with the floor taken off. There the answer was the largest whole number whose square does not exceed n; here the seam between "too small" and "too large" falls between two real numbers and there is no first integer to land on.

## Why the loop cannot be while (hi - lo > eps)

The tidy-looking version is the one that hangs:

while (hi - lo > 1e-9) { ... } // do NOT write this

Once lo and hi are neighbouring doubles their midpoint rounds to one of them, the interval stops shrinking, and the condition never becomes false. At n = 10^9 the gap between neighbouring doubles near the answer is already about 4 * 10^-12, which is close enough to the usual eps to make this a real hazard rather than a theoretical one.

Run a FIXED count instead:

lo = 0, hi = max(1, n) repeat 100 times: mid = (lo + hi) / 2 if mid * mid <= n: lo = mid else: hi = mid print lo with d decimals

One hundred halvings shrink the starting interval by a factor of 2^100, which is about 10^30. A double carries roughly 16 significant digits, so the loop is exact to the limit of the type long before it stops, and it cannot hang.

## Why the bound is max(1, n) and not n

For n >= 1 the root never exceeds n. For n = 0 that would give the empty interval [0, 0], which is harmless, but for the same expression written as hi = n with n between 0 and 1 in a later variant it is wrong: the root of 0.25 is 0.5, larger than the number itself. Taking the maximum with 1 makes the bound correct for every non-negative input and costs one halving.

## Why not just call sqrt

For this exact question a library sqrt is correctly rounded and would do. The reason to write the search is that the very next problem replaces the square with a cube, then with a cubic polynomial, then with a sum of fractions, and the library stops having a function for it. The loop above changes by one line each time.

## What is guaranteed about the printed digits

Every test here has an answer at least 10^-9 away from a halfway point at d digits, so rounding behaves the same in every language. Print with the plain fixed format, never in exponent form.

## Width

At the top of the range mid * mid reaches 10^18. Both sides of the comparison are doubles here, which carry it with room to spare. Rewrite the check with integers and it overflows a signed 32-bit type immediately, since 10^18 is four hundred million times what one holds; it needs a 64 bit type instead.

## Related problems

Problem 248 is the whole-number version of this exact predicate, and problem 1343 raises it to a kth root. Problem 801 takes the same step from whole to real that this problem takes from 248.

## Cost

Time O(100). Space O(1).

Constraints - `0 ≤ n ≤ 10^9` - `1 ≤ d ≤ 6` - every answer is at least `10^-9` away from a halfway rounding point at `d` digits