1397. The Integer Square Root, Without Floating Point
For each query print the largest integer r with r * r ≤ n, that is the
square root of n rounded down.
n = 0 -> 0
n = 15 -> 3
n = 16 -> 4
## What most people try first
(int) sqrt(n), or Math.floor(Math.sqrt(n)). It is one line and it is wrong,
and the reason is worth understanding rather than working around.
A double has a 53-bit mantissa, so it stores about 15 to 16 significant decimal
digits exactly. n here reaches 10^18, which needs 60 bits, so converting
n to a double already loses information before the square root is taken.
Then sqrt rounds again. The result can land just below a true integer root or
just above it, and both failures occur:
``` n = 999999998000000001 = 999999999^2 exactly the double nearest n is not n, and sqrt of it can give 999999998.9999999 taking the floor then answers 999999998, which is one too small
n = 999999999999999999 sqrt as a double can round up to exactly 1000000000.0 taking the floor then answers 1000000000, whose square is 10^18, above n ```
So the error is in both directions, which means no fixed nudge repairs it.
Adding 0.5 fixes the first case and breaks the second. Problem 248 computes
this for small values where a double is exact, and problem 1343 does the kth
root at 10^12; this is the case where the input genuinely exceeds what a
double can hold.
## Binary search on the answer
The predicate r * r ≤ n is monotone: once it fails it fails for every
larger r. So binary search for the last r that satisfies it:
lo = 0, hi = 2000000000
while lo < hi:
mid = (lo + hi + 1) / 2 rounded up
if mid * mid <= n: lo = mid
else: hi = mid - 1
answer lo
The invariant is that lo * lo <= n always holds and (hi+1)^2 > n always
holds, so when they meet, lo is the answer. mid is rounded up because
lo can equal mid and a rounded-down mid would then never advance,
leaving the loop stuck.
hi starts at 2 * 10^9 because sqrt(10^18) is 10^9, so the answer never
exceeds 10^9 and that bound is generous. It also matters for overflow, below.
## An alternative: Newton with an integer correction
Newton's iteration x = (x + n/x) / 2 with integer division converges to
within one of the root, so two correction loops finish the job:
while x*x > n: x = x - 1
while (x+1)*(x+1) <= n: x = x + 1
That is what the oracle for this problem uses, as a second opinion against the
binary search. The correction steps are not optional: integer Newton can
overshoot by one, and shipping it without them is the second most common bug
here after trusting sqrt.
## Overflow
mid * mid is the dangerous expression. With hi = 2 * 10^9 the largest
product formed is 4 * 10^18, which fits in a signed 64-bit integer, whose
limit is about 9.22 * 10^18, but only just: an upper bound of 4 * 10^9
would reach 1.6 * 10^19 and overflow. A signed 32-bit integer stops at
2147483647 and a 32-bit build answers 488908 for n near 10^18. In
JavaScript n is past the 2^53 a Number is exact to, so BigInt is
required, and mid * mid at 4 * 10^18 would be far past it even if n were
not.
## Cost
About 31 iterations per query.
Constraints - `1 ≤ q ≤ 1000` - `0 ≤ n ≤ 1000000000000000000` - No floating point square root may be relied on; the answer must be exact.
Input
The first line contains q.
Each of the next q lines contains one integer n.
Output
For each query print the largest integer r with r * r at most n, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.