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