On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano
<steve+pyt...@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
--
https://mail.python.org/mailman/listinfo/python-list
