On Sat, Aug 5, 2017 at 3:44 AM, Steve D'Aprano <steve+pyt...@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 -- https://mail.python.org/mailman/listinfo/python-list
