Challenge: find the first value where two functions differ
On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano
<steve+python at pearwood.info> wrote:
> def isqrt_float(n):
> """Integer square root using floating point sqrt."""
> return int(math.sqrt(n))
> We know that:
> - for n <= 2**53, isqrt_float(n) is exact;
> - for n >= 2**1024, isqrt_float(n) will raise OverflowError;
> - between those two values, 2**53 < n < 2**1024, isqrt_float(n)
> will sometimes be exact, and sometimes not exact;
> - there is some value, let's call it M, which is the smallest
> integer where isqrt_float is not exact.
> Your mission, should you choose to accept it, is to find M.
Hmm. Thinking aloud a bit here. We know that isqrt_float(n) is not
technically *exact* for any n that is not a square. So what I'd do is
assume that for (n*n+1) to (n+1)*(n+1)-1, it's going to return the
same value. I would then probe every perfect square, and the values
one above and one below it. Now, that's still probably too many to
check, but it's going to be a lot faster; for starters, we don't
actually need to use isqrt_newton to compare against it.
for root in range(2**26, 2**53):
square = root * root
if isqrt_float(square - 1) != root - 1:
print(square - 1)
if isqrt_float(square) != root:
if isqrt_float(square + 1) != root:
print(square + 1)
That gave me this result almost instantaneously:
which has been rounded up instead of down. I don't know if that counts
as sufficiently wrong?
>>> 67108865 ** 2