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. -- https://mail.python.org/mailman/listinfo/python-list
