Challenge: find the first value where two functions differ

[Chris Angelico]

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)
        break
    if isqrt_float(square) != root:
        print(square)
        break
    if isqrt_float(square + 1) != root:
        print(square + 1)
        break

That gave me this result almost instantaneously:

4503599761588224

which has been rounded up instead of down. I don't know if that counts
as sufficiently wrong?

>>> isqrt_float(4503599761588224)
67108865
>>> isqrt_newton(4503599761588224)
67108864
>>> 67108865 ** 2
4503599761588225

ChrisA