Challenge: find the first value where two functions differ
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 :-)
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:
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:
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.
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
py> 94906266**2 > 2**53
 I have only proved this is correct, not tested it.
?Cheer up,? they said, ?things could be worse.? So I cheered up, and sure
enough, things got worse.