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. The integer square root is, *by definition*, the floor (round down to nearest integer, which for positive values is the same as just truncating) of the true square root. So the first few integer square roots are: n=1 isqrt=1 n=2 isqrt=1 n=3 isqrt=1 n=4 isqrt=2 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 That's a difference of just 56 or one part in 14557 trillion, which is *approximately* correct :-) Up to 2**53, there is no rounding error when converting from int to float, which is why I am confident that int(math.sqrt(n)) will always give the exact value of integer square root up to at least 2**53. We have math.sqrt(n) return the correctly rounded true square root, and int() truncates it, which is the definition of integer square root. For example: py> isqrt_float(2**53) 94906265 py> isqrt_newton(2**53) 94906265 They're the same, and I stated earlier that you can take isqrt_newton as always exact. (Perhaps I should have said "correct" rather than exact?) You may be concerned that 94906265**2 != 2**53. That's not a problem. All that matters is that 94906265 is the largest integer which, when squared, is less than or equal to the original 2**53. And that is the case: py> 94906265**2 <= 2**53 True py> 94906266**2 > 2**53 True [1] I have only proved this is correct, not tested it. -- Steve “Cheer up,” they said, “things could be worse.” So I cheered up, and sure enough, things got worse. -- https://mail.python.org/mailman/listinfo/python-list
