[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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. 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.

- Prev by Date:
**Basic sample code, pandas and cython** - Next by Date:
**Challenge: find the first value where two functions differ** - Previous by thread:
**Challenge: find the first value where two functions differ** - Next by thread:
**Challenge: find the first value where two functions differ** - Index(es):