Challenge: find the first value where two functions differ

[Rhodri James]

On 04/08/17 15:51, Steve D'Aprano wrote:
> 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?

I tried a variation of what you used to cut down the search space further:

for j in range(0, 53):
   for i in range(53, 105):
     n = 2**i + 2**j
     if isqrt_newton(n) != isqrt_float(n):
       print(n, i, j)
       sys.exit(1)

which gave me a new upper bound of 2**54+2**28.  Reversing the order of 
the loops would probably have been more sensible, but what the heck. 
That's only (!) 9007199523176448 values to test, which my machine seemed 
to be quite happy with, but you could repeat the exercise with more 
layers if you really wanted to.

-- 
Rhodri James *-* Kynesim Ltd