Challenge: find the first value where two functions differ

[Steve D'Aprano]

On Sat, 5 Aug 2017 01:44 am, Chris Angelico wrote:

> Hmm. Thinking aloud a bit here. We know that isqrt_float(n) is not
> technically *exact* for any n that is not a square. 

I got bogged down in answering that misapprehension, but it may not actually
have mattered. You then said:


> 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.

That's interesting. I think I need to think more about that when it's not stupid
o'clock in the morning, because although I'm not sure your logic is sound I
can't deny that you've hit on a *huge* improvement in the upper bound. You
have:

> 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?

It certainly does!

>>>> isqrt_float(4503599761588224)
> 67108865
>>>> isqrt_newton(4503599761588224)
> 67108864


After running a random search for something like 18 hours, I managed to get the
bound down to 9008783381281320. Ian managed to pick 9007199326062755 (perhaps
by luck?). But you beat us both, handsomely.




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