Challenge: find the first value where two functions differ

[Chris Angelico]

On Sat, Aug 5, 2017 at 3:44 AM, Steve D'Aprano
<steve+python at pearwood.info> wrote:
> 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.

My logic was that floating point rounding is easiest to notice when
you're working with a number that's very close to something, and since
we're working with square roots, "something" should be a perfect
square. The integer square root of n**2 is n, the ISR of n**2+1 is
also n, and the ISR of n**2-1 should be n-1. I actually wanted to
start at 2**53, but being an odd power, that doesn't have an integer
square root, so I started at 2**52, which has an ISR of 2**26.

The phenomenon MAY depend on the current FPU rounding rules.

ChrisA