Challenge: find the first value where two functions differ
Chris Angelico
rosuav at gmail.com
Fri Aug 4 13:48:02 EDT 2017
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
More information about the Python-list
mailing list