Challenge: find the first value where two functions differ
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 :-)
> 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 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)
> py> isqrt_newton(2**119)
>  I have only proved this is correct, not tested it.
And that's what I looked at.
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
This value is lower than 2**53.