osdir.com


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

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 :-)

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.