Challenge: find the first value where two functions differ

[Chris Angelico]

On Sat, Aug 5, 2017 at 3:37 AM, Steve D'Aprano
<steve+python at pearwood.info> wrote:
> On Sat, 5 Aug 2017 01:44 am, Chris Angelico wrote:
>
>> 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))
> [...]
>
>> Hmm. Thinking aloud a bit here. We know that isqrt_float(n) is not
>> technically *exact* for any n that is not a square.
>
> Actually we do. You seem to be thinking about the "true" square root, not the
> integer square root.
>
> I'm sorry, I should have posted a link to the definition of integer square root,
> that's my mistake. But I thought that everyone would either already know, or
> know how to use Wikipedia :-)
>
> https://en.wikipedia.org/wiki/Integer_square_root
>
> Mea culpa.

So my assumption turned out correct, albeit for slightly incorrect
reasons. In any case, I based things on a discrepancy between
isqrt_float and isqrt_newton.

> and isqrt_float is exact for those n. It's definitely[1] exact for all n up to
> 2**53, and many more beyond that. By exact I mean that it returns the same
> (correct) root as isqrt_newton, rather than the root plus (or minus) a bit.
>
> An example of where it is *not* exact:
>
> py> isqrt_float(2**119)
> 815238614083298944
> py> isqrt_newton(2**119)
> 815238614083298888
>
> [1] I have only proved this is correct, not tested it.

And that's what I looked at.

>>> isqrt_float(4503599761588224)
67108865
>>> isqrt_newton(4503599761588224)
67108864

This number is (2**52 + 2**27), and is one less than a square. The
floating-point function is rounding it up, and as such is not
returning the integer square root, which should be rounded down. Is my
analysis correct?

This value is lower than 2**53.

ChrisA