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

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)) > > > > We know that: > > - for n <= 2**53, isqrt_float(n) is exact; > > - for n >= 2**1024, isqrt_float(n) will raise OverflowError; > > - between those two values, 2**53 < n < 2**1024, isqrt_float(n) > will sometimes be exact, and sometimes not exact; > > - there is some value, let's call it M, which is the smallest > integer where isqrt_float is not exact. > > > Your mission, should you choose to accept it, is to find M. Hmm. Thinking aloud a bit here. We know that isqrt_float(n) is not technically *exact* for any n that is not a square. So what I'd do is assume that for (n*n+1) to (n+1)*(n+1)-1, it's going to return the same value. I would then probe every perfect square, and the values one above and one below it. Now, that's still probably too many to check, but it's going to be a lot faster; for starters, we don't actually need to use isqrt_newton to compare against it. for root in range(2**26, 2**53): square = root * root if isqrt_float(square - 1) != root - 1: print(square - 1) break if isqrt_float(square) != root: print(square) break if isqrt_float(square + 1) != root: print(square + 1) break That gave me this result almost instantaneously: 4503599761588224 which has been rounded up instead of down. I don't know if that counts as sufficiently wrong? >>> isqrt_float(4503599761588224) 67108865 >>> isqrt_newton(4503599761588224) 67108864 >>> 67108865 ** 2 4503599761588225 ChrisA

- Prev by Date:
**Challenge: find the first value where two functions differ** - 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):