Challenge: find the first value where two functions differ
Steve D'Aprano
steve+python at pearwood.info
Fri Aug 4 13:37:38 EDT 2017
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.
More information about the Python-list
mailing list