[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: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

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

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