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:47 am, Ian Kelly wrote:

> Here's a much smaller upper bound:
> 
>>>> n = 2 ** 53
>>>> s = isqrt_newton(n)
>>>> n
> 9007199254740992
>>>> s
> 94906265
>>>> m = (s+1)**2 - 1
>>>> m
> 9007199326062755
>>>> isqrt_newton(m) == isqrt_float(m)
> False

Oooh, interesting. How did you get that? By luck, or do you have some reason for
picking (s+1)**2 - 1?


I have managed to find an upper bound *almost* as small:

9008783381281320

by running a script for the last 15 or 16 hours, which randomly tests ints
between lower and upper bound. If it finds a miss, it reduces the upper bound.

That started off very promised, and was extremely fast at first, but as the
range of values to check gets tighter, it also becomes harder to find any
misses.



-- 
Steve
?Cheer up,? they said, ?things could be worse.? So I cheered up, and sure
enough, things got worse.