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

This is a challenge for which I don't have a complete answer, only a partial answer. Here are two functions for calculating the integer square root of a non-negative int argument. The first is known to be exact but may be a bit slow: def isqrt_newton(n): """Integer sqrt using Newton's Method.""" if n == 0: return 0 bits = n.bit_length() a, b = divmod(bits, 2) x = 2**(a+b) while True: y = (x + n//x)//2 if y >= x: return x x = y The second is only exact for some values of n, and for sufficiently large values of n, is will fail altogether: import math 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. Hint: a linear search starting at 2**53 will find it -- eventually. But it might take a long time. Personally I gave up after five minutes, but for all I know if I had a faster computer I'd already have the answer. (But probably not.) Another hint: if you run this code: for i in range(53, 1024): n = 2**i if isqrt_newton(n) != isqrt_float(n): print(n) break you can find a much better upper bound for M: 2**53 < M <= 2**105 which is considerable smaller that the earlier upper bound of 2**1024. But even so, that's still 40564819207303331840695247831040 values to be tested. On the assumption that we want a solution before the return of Halley's Comet, how would you go about finding M? -- Steve ?Cheer up,? they said, ?things could be worse.? So I cheered up, and sure enough, things got worse.

- Prev by Date:
**how to sort a list of tuples with custom function** - Next by Date:
**SSL/TLS support in Pyro4** - Previous by thread:
**how to grep** - Next by thread:
**Challenge: find the first value where two functions differ** - Index(es):